> 从两端分别求以i为尾的最大连续子段和。然后把两端子段和相加求其最大值。。
> 
> #include<iostream>
> using namespace std;
> 
> int a[50010];
> int b[50010];
> int c[50010];
> 
> int main(){
> 	int n,t;
> 	scanf("%d",&t);
> 	while(t--){
> 		scanf("%d",&n);
> 		for(int i=1; i<=n; ++i){
> 			scanf("%d",a+i);
> 		}
> 		
> 		for(int i=1; i<=n; ++i){
> 			if(i==1){
> 				b[i]=a[i];
> 			}
> 			else{
> 				if(b[i-1]>0){
> 					b[i] = a[i]+b[i-1];
> 				}
> 				else{
> 					b[i]=a[i];
> 				}
> 			}
> 		}
> 		
> 		for(int i=2;i<=n; ++i){
> 			if(b[i]<b[i-1])b[i]=b[i-1];
> 		}
> 		
> 		for(int i=n; i>=1; --i){
> 			if(i==n)c[i]=a[i];
> 			else{
> 				if(c[i+1]>0){
> 					c[i]=c[i+1]+a[i];
> 				}
> 				else{
> 					c[i]=a[i];
> 				}
> 			}
> 		}
> 		
> 		for(int i=n-1; i>=1; --i){
> 			if(c[i]<c[i+1])c[i]=c[i+1];
> 		}
> 		
> 		int max=b[1]+c[2];
> 		for(int i=2; i+1<=n; ++i){
> 			if(max<b[i]+c[i+1])max=b[i]+c[i+1];
> 		}
> 		printf("%d\n",max);
> 	}
> 	return 0;
> }
> 
   代码要这么解释的话肯定有问题,可能会重复计算中间的公共部分, 正确的解释应该是
  b[i]表示i为尾巴的最大连续和,c[i]表示i为头部的最大连续和, 第2次处理后
  b[i]表示前i个元素的最大连续和,c[i]表示i~n元素的最大连续和