> #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+（附代码，请指教） (50) 351200 2011-10-26 20:05:08