问题ID POJ2479
Maximum sum
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 28229 | Accepted: 8626 |
Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
Your task is to calculate d(A).
Input
The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample Input
1 10 1 -1 2 2 3 -3 4 -4 5 -5
Sample Output
13
Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.
解答:解这道题我用到了求连续子串最大和的问题(以前写过),分别从不同的位置将原数据划分成两个子串,然后分别求最大连续子串和,然后求和,最后比较输出最大值。(动态规划思想,使用sumCal[100][100]保存中间结果)
#include <iostream> using namespace std; int data[32]; int sumCal[100][100]; int n; int calmax(int low,int high)//求连续子串最大和的函数; { if(sumCal[low][high]!=0) return sumCal[low][high]; int maxTohere=0, maxAll=0; for(int i=low; i<=high; i++) { maxTohere += data[i]; if(maxTohere<0) maxTohere=0; if(maxTohere>maxAll) maxAll=maxTohere; } sumCal[low][high]=maxAll; return sumCal[low][high]; } int divide( int k) { int sum1=0,sum2=0,sum=0; sum1=calmax(0,k); sum2=calmax(k+1,n-1); sum=sum1+sum2; return sum; } int main() { memset(data,-1,sizeof(data)); cin>>n; for(int i=0; i<n; i++) cin>>data[i]; int max=0, tmp=0; for (int j=0; j<n; j++) { tmp=divide(j);//从不同位置划分成两个子串 if(tmp>max) max=tmp; } cout<<max; }