/*Maximum sumTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 20864 Accepted: 6326Description
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.Output
Print exactly one line for each test case. The line should contain the integer d(A).Sample Input
1
101 -1 2 2 3 -3 4 -4 5 -5Sample Output
13Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.Source
POJ Contest,Author:Mathematica@ZSU
分析：最大两区间。。。
*/
#include <cstdlib> #include <iostream> using namespace std; int main(int argc, char** argv) { int t,m,i,a[50005],f[2][50005]; scanf("%d",&t); while(t--) { scanf("%d",&m); int sum=0,Max=INT_MIN; for(i=1;i<=m;++i)scanf("%d",&a[i]); for(i=1;i<=m;++i) { sum+=a[i]; Max=Max>sum?Max:sum; if(sum<0)sum=0; f[0][i]=Max; } for(i=m,sum=0,Max=INT_MIN;i>0;--i) { sum+=a[i]; Max=Max>sum?Max:sum; if(sum<0)sum=0; f[1][i]=Max; } for(i=1,sum=INT_MIN;i<m;++i) sum=max(sum,f[0][i]+f[1][i+1]); printf("%d/n",sum); } return 0; }
