这是个非常常见的算法题，见诸于《编程之美》、《编程珠玑》等经典算法书籍（亦或，经典面试书籍:)）。网上有很多关于这个问题的讨论和实现，我谨在此写下自己的理解，可能之前有人写过，但毕竟是自己思考出来的东西，权当记录一下。
问题：一个有N个整数元素的一维数组（A[0],A[1].....,A[n-1]），这个数组当然有很多个子数组(n*n个)，求最大的子数组之和。
经典解法：
1
maxsofar=
0
2
maxendinghere=
0
3
for
i=[
0
,n)
4
maxendinghere=max(maxendinghere+a[i],
0
)
5
maxsofar=max(maxendinghere,maxsofar)
在此我写的是《编程珠玑》上的伪代码，我认为这个伪代码以及Bentley的解释最好的诠释了这个问题。
Bentley写到: The key to understanding this program is the variable maxendinghere.这个算法是典型的动态规划算法，表述如下：
我们在计算前i个数的最大子数组和时，先记录前i-1个数的最大子数组之和Max i-1 。当我们遇到新的数A[i]时，如果A[i]的加入会使得某个子数组的和大于前i-1个数的最大子数组和，则更新Max i =该子数组的和，否则，Max i =Max i-1 .接下来我们只需要考虑，A[i]的加入可能会使哪个子数组的和增加？当然是以i-1个数结尾的子数组。所以，在计算前i个数的最大子数组之和时，我们除了要记录前i-1个数的最大子数组之和，还应该记录以i-1个数结尾的最大子数组之和。算法如下：
假设我们已经知道了前i-1个数组的最大子数组为A[j],....,A[k]，其和为Sum k ,同时我们记录以i-1为结尾的最大子数组为A[m],...,A[i-1]，其和为Sum i-1 ，显然，Sum i-1 <=Sum k 。
当遇到第i个数时，如果A[i]>0，则Sum i-1 +A[i]可能会大于Sum k .所以我们更新前i个数的最大子数组之和为：max{Sum i-1 +A[i],Sum k }.
然后我们还应该更新以i结尾的最大子数组之和：Sum i =max{Sum i-1 +A[i],0}.亦即，如果Sum i-1 +A[i]大于0，则以i结尾的最大子数组为A[m],...,A[i-1],A[i]。否则，若Sum i-1 +A[i]小于等于0，则该子数组的和还不如一个空的子数组的和0，将该子数字重置为空，其和为0.
这个经典问题有一个很类似的变种：即同样给定一个数组，写一个在其中找出不连续子数组和的最大值，也就是说子数组里的任意相邻的两个元素，在原数组里都必须是不相邻的才行。同样以数组{1, -2, 3, 5, -1, 2}为例，则和最大的不连续子数组是{1, 5, 2}，函数返回值是8。
有了第一个问题的解答，第二个问题应该很简单。我们考虑下，假设我们已经知道了前i-1个数的数组的不连续子数组和的最大值，当第i个数加入时，这个不连续子数组和在什么情况下会改变？
第i个数加入后不能与以i-1结尾的最大不连续子数组连接，这样会违反不连续的规则。所以我们要考虑结尾最大为i-2的和最大的不连续子数组，设其和为Sum i-2 .当Sum i-2 +A[i]大于以第i-1个数结尾的不连续子数组和的最大值时，我们更新前i个数组成的数组的不连续子数组和的最大值为Sum i-2 +A[i]。算法的代码为：
1
for
(
int
i=2;i<length;i++
){
2
maxendingi=max(maxendingi_2+
array[i],maxendingi_2,maxendingi_1);
3
int
tmp=
maxendingi_2;
4
maxendingi_2=
max(maxendingi_1,maxendingi_2);
5
maxendingi_1=max(tmp+array[i],array[i]);
6
}
其中maxendingi表示前i个数组成的数组的最大不连续子数组的和。
maxendingi_2记录的是结尾最大为i-2的和最大的不连续子数组的和，初始化为array[1]。
maxendingi_1记录的是以i-1结尾的最大的不连续子数组的和,初始化为array[2]。
数组长度小于3的情况可以另行处理。
参考文献：
[1] Jon Bentley 编程珠玑 p81
