本文为经典动态规划问题，数组的最大序列和和的延伸。第一次看见这个题，用了端点枚举的方法，复杂度为0(n^2)。超时严重。参考九度Online Judge_1527: 首尾相连数组的最大子数组和
这篇文章才明白O(n)的算法。
题目描述： 给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。 输入： 输入包含多个测试用例，每个测试用例共有两行，第一行是一个整数n（1=<n<=100000），表示数组的长度，第二行依次输入n个整数（整数绝对值不大于1000）。 输出： 对于每个测试用例，请输出子数组和的最大值。 样例输入： 6 1 -2 3 5 -1 2 5 6 -1 5 4 -7 样例输出： 10 14
题目源地址：http://ac.jobdu.com/problem.php?pid=1527
该题需要证明：对于首尾相连的数组，划去其最大子数组和包含的数组元素，剩下的子数组必然是最小子数组和。可用反证法证明：
假设对于数组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中较大者。
AC代码：
#include <stdio.h> int main() { int n; int list[100010]; int max, min, sumMax, sumMin; int total; while(scanf("%d", &n) != EOF) { scanf("%d", &list[0]); max = sumMax = list[0] > 0 ? list[0] : 0; min = sumMin = list[0] < 0 ? list[0] : 0; total = list[0]; for(int i = 1; i < n; i++) { scanf("%d", &list[i]); if(sumMax > 0) sumMax += list[i]; else sumMax = list[i]; if(sumMin < 0) sumMin += list[i]; else sumMin = list[i]; max = sumMax > max ? sumMax : max; min = sumMin < min ? sumMin : min; total += list[i]; } int tmp = total - min; printf("%d ", max > tmp ? max : tmp); } return 0; } /************************************************************** Problem: 1527 User: Qinger Language: C++ Result: Accepted Time:70 ms Memory:1340 kb ****************************************************************/
在九度论坛上，鬼M给出的是O（nlogn）的算法。。因为对线段树不太了解。所以先放在这里，有时间再看（希望如此）：
题目1：首尾相连数组的最大子数组和 这个题目在之前的最大子段和的基础上扩展了一下，而且数据范围又比较大，不能通过枚举端点来实现题目要求的复杂度。 对于这种循环的问题比较常见的一种方法是把这个数组扩大一倍。 设原来的数组是a[],下标从1开始，为了方便设a[0]=0。 sum[0]=0; sum [ i ]=a[1]+a[2]+a[3]+...+a [ i ] (for each 1<=i<=2*n) 然后我们求出以i为结尾的最大子段和。这个要从前面找一个j,使得sum [ i ] -sum[j]最大，而且i-j<=n,即要求最多只能有n个连续的数字 也就是从区间[i-j,i-1]里面找一个sum的最小值，这个可以用线段树来实现。 因此，这题可以用nlogn的复杂度解决了。当然此题还有其它的解法。有o(n)的，大家可以自行百度。
线段树：http://dongxicheng.org/structure/segment-tree/
#include<stdio.h> #include<math.h> #include<string.h> #include<map> #include<algorithm> #include<queue> using namespace std; const int MAX=110000*2; int sum[MAX]; struct Q { int id,v; }q[MAX]; int front; int rear; void push(int id,int v) { rear++; q[rear].id=id; q[rear].v=v; while(rear-1>=front&&q[rear-1].v>q[rear].v) { rear--; q[rear]=q[rear+1]; } } int query(int id) { while(front<=rear&&q[front].id<id) { front++; } if(front>rear)return 0; return q[front].v; } int main() { int n; int i; int CS=1; while(scanf("%d",&n)!=EOF) { sum[0]=0; for(i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i+n]=sum[i]; } for(i=1;i<=2*n;i++)sum[i]+=sum[i-1]; rear=-1; front=0; push(0,0); int ans=0; for(i=1;i<=2*n;i++) { int tmp=sum[i]-query(i-n+1); if(tmp>ans)ans=tmp; push(i,sum[i]); } printf("%d ",ans); } return 0; } /************************************************************** Problem: 1527 User: 鬼M Language: C++ Result: Accepted Time:70 ms Memory:3600 kb ****************************************************************/