求最長子段和問題，但是是求兩段的子段和。
也就是對每個i來說，求出[0~i-1]的最大子段和以及[i~n-1]的最大子段和，再相加起來。
求最大的一個就行了。
[0~i-1]的最大子段和從左向右掃描，[i~n-1]從右向左掃描即可。
時間復雜度為O(n).
在輸入的時候，開始用的是iostream，結(jié)果超時，要用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;
}