求最长子段和问题，但是是求两段的子段和。
也就是对每个i来说，求出[0~i-1]的最大子段和以及[i~n-1]的最大子段和，再相加起来。
求最大的一个就行了。
[0~i-1]的最大子段和从左向右扫描，[i~n-1]从右向左扫描即可。
时间复杂度为O(n).
在输入的时候，开始用的是iostream，结果超时，要用scanf。497ms...
#include <cstdio>
#include <algorithm>
using namespace std;
int v[50001];
int left[50001];
int right[50001];
void solve()
{
int casessize;
scanf("%d",&casessize);
while(casessize--){
int size;
scanf("%d",&size);
for(int i=0;i<size;++i)
scanf("%d",&v[i]);
// 此时left[i] 为包含i最大子段和
left[0] = v[0];
for(int i=1;i<size;++i){
if(left[i-1]<0)
left[i] = v[i];
else
left[i] = left[i-1]+v[i];
}
// 此时left[i] 为i左边最大子段和
for(int i=1;i<size;++i)
left[i] = max(left[i],left[i-1]);
right[size-1] = v[size-1];
for(int j=size-2;j>=0;j--){
if(right[j+1]<0)
right[j] = v[j];
else
right[j] = right[j+1]+v[j];
}
for(int i=size-2;i>=0;i--)
right[i] = max(right[i+1],right[i]);
int res = INT_MIN;
for(int i=1;i<size;++i){
res = max(res,left[i-1]+right[i]);
}
printf("%d\n",res);
}
}
int main()
{
solve();
return 0;
}