#include<cstdio>
int t,n,a[50000],b[50000],c[50000],i,temp,max;
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=0;i<n;i++)scanf("%d",&a[i]);
		b[0]=temp=a[0];
		for(i=1;i<n;i++){
			temp=a[i]+temp>a[i]?a[i]+temp:a[i];
			b[i]=temp>b[i-1]?temp:b[i-1];
		}
		c[n-1]=temp=a[n-1];
		for(i=n-2;i>=0;i--){
			temp=a[i]+temp>a[i]?a[i]+temp:a[i];
			c[i]=temp>c[i+1]?temp:c[i+1];
		}
		max=b[0]+c[1];
		for(i=2;i<n;i++)max=b[i-1]+c[i]>max?b[i-1]+c[i]:max;
		printf("%d\n",max);
	}
}

• Re:弱问100+MS的大牛是如何做的~~我O(n)的做法也400+（附代码，请指教） (565) 351200 2011-10-26 20:03:37
  • Re:弱问100+MS的大牛是如何做的~~我O(n)的做法也400+（附代码，请指教） (50) 351200 2011-10-26 20:05:08
• Re:弱问100+MS的大牛是如何做的~~我O(n)的做法也400+（附代码，请指教） (565) WsndNmsl 2014-06-03 14:49:32