问题
求最大连续子序列的问题描述如下：
给定一个实数序列 x1, x2, … , xn（不必是正数），寻找一个（连续的）子序列 xi, xi+1, … , xj，使得其数值之和在所有连续子序列数值之和中是最大的。
这个问题就是最大子序列问题，所求的的这个序列就叫做——最大子序列。下面通过数学归纳法来分析和解决这个问题，解决这个问题的最好目标是： 一个算法，能够只扫描此序列一次就得到最大子序列。
归纳分析
根据上面的问题可以直接得到一般的归纳假设：
归纳假设： 已知如何找到规模小于 n 的序列的最大子序列。
下面假定一些变量：
- 给定序列 S(n)=(x1, x2, … , xn).
- 序列 S(n) 的子序列为 S’(n) .
- 序列 S(n) 的最大子序列为 S’M(n)=(xi, xi+1, … , xj).
- 序列 S(n) 的最大后缀子序列为 S’E(n)=(xk, xk+1, … , xn).
现在开始用数学归纳法来证明：
- 当 n ＝ 1 时， S(1)=x1，如果 x1<0，则 S’M(1)＝NULL；否则 S’M(1)＝x1 .
- 当 n = n-1 时，S(n-1)=(x1, x2, … , xn-1)，假设 S’M(n-1)=(xi, xi+1, … , xj).
当 n = n 时，S(n)=(x1, x2, … , xn)=( S(n-1), xn)，然后由 S’M(n-1) 推导出 S’M(n)，共有下面3种情况：
- S‘M(n-1)=(xi, xi+1, … , xj) ＝ NULL，如果 xn<0，则 S’M(n)＝NULL；否则 S’M(n)＝xn .
- S‘M(n-1)=(xi, xi+1, … , xj) && j = n-1，此时 S’M(n-1) ＝ S‘E(n-1)，如果 xn > 0，S’M(n)＝ S’M(n-1) + xn ＝ (xi, xi+1, … , xj) + xn，否则 S‘M(n)＝ S’M(n-1)=(xi, xi+1, … , xj) .
- S‘M(n-1)=(xi, xi+1, … , xj) && j < n-1，此时 S’M(n-1) > S‘E(n-1)，则可得到 S’M(n)＝S’M(n-1) 或者 S‘M(n)＝S’E(n-1) + xn .
即上述可得证：能够求出 S(n)=(x1, x2, … , xn) 的最大连续子序列，不过上述的证明过程中用了增强归纳假设，这个也是这个证明的关键：
更强的归纳假设： 已知如何找到规模小于 n 的序列的最大子序列，以及作为后缀的最大子序列。
我们知道了 S’M(n) 和 S’E(n) 这两个序列，算法也就明确了。我们把 xn 加入到最大后缀子序列中，如果它的和大于原来的最大子序列，则得到一个新的最大子序列（同样也是一个后缀），否则，保留以前的最大子序列。但求解过程还没有结束，我们还需要寻找新的最大后缀子序列，因为不能只是简单的把 xn 加到以前的最大后缀中，有可能以 xn 结束的最大后缀的和是负数，在这种情况下，我们就需要把NULL（空集）作为最大后缀（以及把随后的 xn+1 也考虑进去）。
具体算法实现
根据上面的分析过程，下面贴上具体的C++代码：
int Maximum_Consecutive_Subsequence(int *x, int n)
{
int global_Max = 0; // 最大子序列的和
int suffix_Max = 0; // 最大后缀子序列的和，每次迭代都会更新
int i = 0;
for (i = 0; i < n; i++)
{
if (x[i] + suffix_Max > global_Max)
{
suffix_Max = suffix_Max + x[i];
global_Max = suffix_Max;
}
else if (x[i] + suffix_Max > 0)
{
suffix_Max = suffix_Max + x[i];
}
else
{
suffix_Max = 0;
}
}
return global_Max;
}更详细的代码可以戳这里.
2014.09.07