最大连续子序列和最早是在编程珠玑讲述，这个问题最初由布朗大学的统计学家UIF Grenander在处理图片时提出的，当时是处理二维数组的子数组，为了简化问题，才先提出一维数组的解法。
问题定义：对一个有n个元素的数组，求最大的连续子数组的和。数组的元素必然有正数也有负数才有意义，如果全是正数，那最大的子数组就是本身；如果全部为负数，那最大子数组就是空数组。例如下面的数组，其最大子数组序列和为187，子数组为X[2,..,6]：
31
-41
59
26
-53
58
97
-93
-23
84
这个问题有很强的代表性，有很多实现方法，复杂度从O(n^3)到O(n)都用，另外这个问题可以扩展到二维数组，甚至扩展到环，我们来逐一讨论，步步深入。
1、最直接的方法O(n^3)
每个问题往往都有一个最直接而鲁莽的方法，虽然这样的方法不是我们最终想要的，但直接有效的方法能启发我们进一步优化。这里最直接的方法就是遍历所有的子数组，比较每一个子数组的和即得到最大的子数组和。实现代码如下，只需要记录一个当前最大值即可。
复制代码
1 def maxSeqSum1(data):
2 n = len(data)
3 maxsofar = 0
4 for i in xrange(n):
5 for j in xrange(i,n):
6 s = sum(data[i:j+1])
7 if s > maxsofar:
8 maxsofar = s
9 return maxsofar
复制代码
这个算法的时间复杂度是O(n^3)，虽然看上去只要两层循环，但最里面的求和并不是常量时间。最外层循环n次，第二层最多循环n次，里面的求和长度最大也为n，因此整个计算的复杂度是O(n^3)。
2、小小的改进O(n^2)
当数组长度大于1000后，O(n^3)的算法就已经显得力不从心了。想一想我们可以稍作改变就降低到O(n^2)，这里需要比较的子数组个数为n*(n-1)/2，已经是n^2的数量级了，因此我们想能不能在求和上做改进，使得求子数组的和的复杂度为O(1)。上面的算法的i、j分别是子数组的上边界和下边界，子数组X[i,..j]的和sum(X[i,..j]) = sum(X[i,..j-1])+X[j]，于是得到如下的算法：
复制代码
1 def maxSeqSum2(data):
2 n = len(data)
3 maxsofar = 0
4 for i in xrange(n):
5 s = 0
6 for j in xrange(i,n):
7 s += data[j]
8 if s > maxsofar:
9 maxsofar = s
10 return maxsofar
复制代码
还有另外一种方法，将计算子数组的和的复杂度降到O(1)，它先用数组accu[n]表示累加和，即accu[i]表示X前i个元素之和，这样sum(X[i,..j])=accu[j]-accu[i-1]，实现代码如下：
复制代码
def maxSeqSum3(X):
'''maxSeqSum3 O(n^2)'''
n = len(X)
accu = [0] * (n+1)
for i in xrange(n):
accu[i] = accu[i-1] + X[i]
maxsofar = 0
for i in xrange(n):
for j in xrange(i,n):
s = accu[j] - accu[i-1]
if s > maxsofar:
maxsofar = s
return maxsofar
复制代码
这里利用了python的一个特别之处，即列表下标可以为负数，x[-1]即为x[n-1]，用C语言实现需要修改一下，我们可以用accu[i+1]表示前i个元素之和，这样C代码如下：
复制代码
1 int maxSeqSum3(int X[],int n){
2 int accu[n+1];
3 accu[0] = 0;
4 for(int i=0 ; i < n; i++)
5 accu[i+1] = accu[i] + X[i];
6 int s,maxsofar = -1;
7 for(int i = 0; i < n; i++){
8 for(int j =i; j < n; j++){
9 s = accu[j+1]-accu[i];
10 if(s > maxsofar)
11 maxsofar = s;
12 }
13 }
14 return maxsofar;
15
16 }
复制代码
3、更近一步的方法O(nlog(n))
O(n^2)的复杂度还是太高，当n大于10,000后，需要等待的计算时间就已经超过8分钟了。如果能把这个问题规模分解成两个子问题，那就能转化为递归问题，很可能就能得到一个O(nlog(n))的算法。实际上，我们把原来的数组X[0,...n)分成两个等长的子数组X1和X2：
X1
X2
原数组X的最大连续子数组只能是以下三种情况之一：
只在X1中，即X的最大和连续子数组就是X1的最大和连续子数组m1;
只在X2中，即X的最大和连续子数组就是X2的最大和连续子数组m2;
m1
m2
即在X1中又在X2中，如m3所示
m3
X1和X2的最大和连续子数组m1、m2可以通过递归来求解，现在我们只需要把m3求出来，比较其中的最大值就得到了X的最大和。不知道大家能否理解，m3是X1右边的一个子数组之和加上X2左边一个子数组之和。递归求解问题需要定义平凡解，即当子数组的长度为0时，最大和应该为0，当子数组长度为1时，最大和应该为max(xi[0],0)。这样我们便实现了一个递归的解法：
复制代码
1 def recursionMax(X,l,u):
2 if l > u:#lenght is 0
3 return 0
4 if l == u:
5 return max(X[l],0)
6 m = (l + u) / 2
7 lmax = s = 0
8 for i in xrange(m,l,-1):
9 s += X[i]
10 lmax = max(lmax,s)
11 rmax = s = 0
12 for i in xrange(m+1,u-1):
13 s += X[i]
14 rmax = max(rmax,s)
15 return max(rmax+