POJ 2479

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=50005;
const int M=1<<31;
int t,n,sum,ans;
int a[N],Max[N];

int main(){
	scanf("%d",&t);
	while(t--){
		int tmp=M;
		sum=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
			sum+=a[i];
			if(sum>tmp)
				tmp=sum;
			Max[i]=tmp;
			if(sum<0)
				sum=0;
		}
		ans=M;
		tmp=M;
		sum=0;
		for(int i=n-1;i>0;i--){
			sum+=a[i];
			if(sum>tmp)
				tmp=sum;
			sum=sum>=0?sum:0;
			if(tmp+Max[i-1]>ans)
				ans=tmp+Max[i-1];
		}
		printf("%d\n",ans);
	}
	return 0;
}