最大连续和，也称最大连续子段和。这个问题虽然简单，但其中蕴含了很多算法的思想，包括动态规划和分治法。
问题描述
最大连续和问题 给出一个长度为n的序列A0,A1,...,An-1，求最大连续和。也就是，要求找到一组(i,j)满足0≤i≤j≤n-1，使得Ai+Ai+1+...+Aj尽量大。
解法1 暴力枚举
我们可以枚举出所有的连续和，记B(i,j)=Ai+Ai+1+...+Aj，也就是 i 从0取到n-1，j 从 i 取到n-1。因此，我们要做的分为两部分，第一部分是枚举出所有的B(i,j)，第二部分是对于具体的B(i,j)计算它的值，计算B(i,j)的值的时间花费为j-i+1，因此总的时间复杂度为
(T(n)=sum_{i=0}^{n-1}sum_{j=i}^{n-1}(j-i+1)=frac{n(n+1)(n+2)}{6}=Theta(n^3))
具体实现如下（python代码）
def get_max_continue_sum(A):
n=len(A)
best=A[0]
for i in xrange(n):
for j in xrange(i,n):
B_ij=sum(A[i:j])
if best<B_ij:
best=B_ij
return best
一点改进方法
这里包含一点动态规划的思想。
计算连续和的时候，我们使用公式B(i,j)=Ai+Ai+1+...+Aj。也就是说，我们需要j-i+1步才能计算出B(i,j)，但是这是没有必要的。
设前缀和S(i)=A0+A1+...+Ai，那么有B(i,j)=S(j)-S(i-1)。有了这个式子，我们就可以通过前缀和计算连续和。改进后的算法的时间复杂度(T(n)=Theta(n^2))。
具体代码如下
def get_max_continue_sum(A):
n=len(A)
S=[A[0]]
for i in xrange(1,n):
Si=S[i-1]+A[i]
S.append(Si)
best=A[0]
for i in xrange(n):
for j in xrange(i,n):
B_ij=S[j]-S[i-1]
if best<B_ij:
best=B_ij
return best
解法2 分治法
分治的英文是Divide and Conquer，也就是将问题划分为多个子问题，然后分别解决。
思路 对于一个序列{A0,A1,...,An-1}中的一个元素Ak，假设最大字段和为B(i,j)，那么存在两种情况，A[i:j]要么包括Ak，要么不包括Ak。如果A[i:j]要么包括Ak，那我们怎么求B(i,j)呢？B(i,j)=B(i,k-1)+Ak+B(k+1,j)，这也就是说，通过一遍扫描，就求出包含元素k的最大字段和，时间花费为(O(n))（原本会花费(O(n^2))的时间，想一想为什么）。
于是，我们将一个序列划分为左半和右半两部分，分别求出相应的最大字段和B1和B2，同时求出起点位于左半、终点位于右半的最大连续和B3，那么该序列的最大字段和B=max(B1,B2,B3)。
比如序列{-2,4,5,-1,-6,9,-1,3}，我们将它划分为两部分{-2,4,5,-1}和{-6,9,-1,3}，那么B1=4+5=9,B2=9-1+3=11,B3=(4+5-1)+(-6+9)=11，因此B=max(9,11,11)=11。
要说明的是，在求B1和B2时，我们使用的方法是调用函数本身。因此，此方法的时间复杂度(T(n))满足(T(n)=T(n/2)+O(n))，解得(T(n)=nlog(n))。
具体实现如下
#python 2.7
def get_max_continue_sum(A):
n=len(A)
k=n/2
B1=get_max_continue_sum(A[:k])
B2=get_max_continue_sum(A[k:])
L_best=_get_best_of_left(A[:k])
R_best=_get_best_of_right(A[k:])
B3=L_best+R_best
return max(B1,B2,B3)
def _get_best_of_left(A):
n=len(A)
v=A[-1]
best=v
for i in xrange(n-2, 0 ,-1):
v+=A[i]
best=max(best,v)
return best
def _get_best_of_right(A):
n=len(A)
v=A[0]
best=v
for i in xrange(1, n):
v+=A[i]
best=max(best,v)
return best
解法3 动态规划法(1)
这个方法是在解法1的改进的基础上，进行改进的。
思路 由于有B(i,j)=S(j)-S(i-1)。假设B(i,j)是最大字段和，那么说明S(j)足够大，S(i-1)也足够小。
于是，我们可以找出使得S(j)最大的j，和使得S(i-1)最小的i。但是并不能这么做，因为如果i>j那就尴尬了。正确的做法是，对于一个 j，在[0,j]的范围内寻找最小的S。
具体实现如下
def get_max_continue_sum(A):
n=len(A)
S=[A[0]]
for i in xrange(1,n):
Si=S[i-1]+A[i]
S.append(Si)
best=A[0]
minS=A[0]
for j in xrange(1,n):
best=max(best,S[j]-minS)
minS=min(minS,S[j])
return best
很容易得到，这种方法的时间复杂度是O(n)。
解法4 动态规划法(2)
我没有想到竟然还有一种时间复杂度为O(n)的算法，直到我看了这篇博客——最大连续区间和的算法总结。
我们定义maxn[i]为以i为结尾的最大连续和，则很容易找到递推关系：maxn[i]=max{0,maxn[i-1]}+a[i]。
因此
def get_max_continue_sum(A):
n=len(A)
best=A[0]
maxn=A[0]
for j in xrange(1,n):
maxn=max(0,maxn)+a[j]
best=max(best,maxn)
return best