做题感悟：这题开始比赛时就在想，又过了几天再去看这题还是没想出了
，终于忍不住百度了一下。
解题思路：该题须要证实：对于首尾相连的数组，划去其最大子数组和包含的数组元素，剩下的子数组必定是最小子数组和。
可用反证法证实：假设对于数组list[1...n]，剩下的子数组不是最小子数组和。因为数组是首尾相连的，我们必定可以假设S1[1...i]为剩下的子数组，S2[i+1...n]为最大子数组
（S1和S2可代表子数组和的含义）。
case1 : S1>=0，则S1+S2为最大子数组和，与前提冲突。
case2 : S1<0，但不是最小子数组和序列。假设Sx为最小子数组和序列。
1）若是S2包含Sx，则S2必定不便是Sx。可将S2分为三项目组。S2[i+1...n] = Sl[i+1...j] + Sx[j+1...k] + Sr[k+1...n].那么因为Sx < S1.则从头组合。Sr + S1 + Sl > Sl + Sx + Sr = S2.与前提抵触。
2）若是S1包含Sx.但不便是Sx可以将S1分为三项目组。S1[1..i] = Sl[1..j] + Sx[j+1...k] + Sr[k+1...i]。那么因为Sx < S1.所以Sl+Sr = S1-Sx > 0.从头组合，则Sr + S2 + Sl > S2..与前提抵触。
3）若是Sx横跨S1和S2.那么可以将S1和S2分别分为两项目组。Sl[1...j]， Sm[j+1...i]， Sn[i+1...k]， Sr[k+1...n].且S1= Sl + Sm;S2 = Sn +Sr;Sx = Sm +Sn..因为Sx < S1，所以Sm < Sl.那么从头分列组合后Sr + Sl > Sr + Sm。与前提抵触。
综上所述，结论得证。
所以我们只需评论辩论两者景象：
1）在首尾不相连的数组中，最大子数组和max.
2）在首尾相连的数组中，求最大子数组和，可以先求首尾不相连的数组中，最小子数组和min。然后Sum - min即为最大子数组和。结果即为max和Sum - min中较大者。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
const double PI = 3.1415926 ;
const double INF = 99999999 ;
const int MX =40 ;
int main()
{
int n,x,max,min,tol,summax,summin ;
while(~scanf("%d",&n))
{
scanf("%d",&x) ;
max = summax= x > 0 ? x : 0 ;
min = summin= x < 0 ? x : 0 ; // 求最小和
tol=x ;
for(int i=0 ;i<n-1 ;i++)
{
scanf("%d",&x) ;
tol+=x ;
summax > 0 ? summax+=x : summax=x ;
summin < 0 ? summin+=x : summin=x ;
max = max < summax ? summax : max ;
min = min > summin ? summin : min ;
}
printf("%d\n",tol-min > max ? tol-min : max) ;
}
return 0 ;
}