#include<iostream>
using namespace std;
int num[100];
int a,s;
int MAX;
void search(int i,int sum)
{
int j;
if(i==a)//到达终点的处理
{
if(sum*(s-sum)>MAX)
MAX=sum*(s-sum);
}
else
for(j=0;j<2;j++)//各个支路
{
//理论上应当添加条件判断
search(i+1,sum+j*num[i-1]);
}
}
int main()
{
int b,c,sum;
while(cin>>a)
{
sum=0;
s=0;
MAX=0;
for(b=0;b<a;b++)
{
cin>>num[b];
s+=num[b];
}
search(0, sum);//从这里开始
cout<<MAX<<endl;
}
}
还有一点启发，max不能用，可以用MAX，无需记录
There are multiple test cases, the first line of each test case is a integer n. (2<=n<=20) The next line have n integers (every integer in the range [1,1000]). We can divide these n integers into two parts and get the sum of the integers in these two parts, define them as sumA and sumB. Please calc the max number of sumA*sumB and output it in a single line.
Sample Input
3
5 3 7
2
4 9
Sample Output
56
36
Hint
(5,3),(7) sumA=8 sumB=7 sumA*sumB=56
(5),(3,7) sumA=5 sumB=10 sumA*sumB=50
(3),(5,7) sumA=3 sumB=12 sumA*sumB=36
(),(3,5,7) sumA=0 sumB=15 sumA*sumB=0
The max is 56.
posted on 2009-05-12 22:18
luis 阅读(315)
评论(0) 编辑 收藏 引用 所属分类:
搜索