最大子序列和O(N)算法简单分析『神兽必读』

对于一个全为负数的序列，最长公共子序列的和值应该是0，理由在于，由0个整数所组成的空子序列也是一个子序列——最大子序列和问题从O（N^3）到线性的算法

其他情况大家也能理解了。 先看算法，算法来自《数据结构与算法分析——C语言描述》

int
MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, j;
    for(j = 0; j < N; j++) /*1*/
    {
        ThisSum += A[j];   /*2*/
        
        if(ThisSum > MaxSum) /*3*/
            MaxSum = ThisSum; /*4*/
        else if(ThisSum < 0) /*5*/
            ThisSum = 0;   /*6*/
    }
    
    return MaxSum;
}

可以看到算法中重要的位置都标注出来了。 显然这个算法有一个for循环，整体时间复杂度可以看作O(N)。 就算法正确性来分析，首先假设这样的输入：-2, -3, 5, 6, -1, 8, 9

1. 扫描到-2或-3的时候，执行/*2*/，/*5*/条件成立，所以执行/*6*/，此时ThisSum依然是0，MaxSum也是0

为什么不把开头的负数也加和到最大子序列的和中去呢，显然我们做一个假设就很明显了，如-1, 1, 2, 3, 4, 5，没有开头的-1结果更大。

1. 继续扫描5, 6，执行/*2*/，/*3*/条件成立，所以执行/*4*/，此时ThisSum是11，MaxSum也是11
2. 继续扫描到-1，执行/*2*/，ThisSum变成了10，此时条件/*3*/和/*5*/都不成立，所以MaxSum仍然是11，只不过ThisSum变小了
3. 继续扫描到8，执行/*2*/，ThisSum变成18，此时条件/*3*/成立，执行/*4*/，MaxSum从上一次结果的11变成18。
4. 依此类推

我想这个分析就到此结束了。

UPDATE 或许你会想到了，有时候最大子序列和是某一小段的话，比如是后半段，但是这个算法明显给人的感觉就是一路加和过来呀，好像是认为越长的子序列和越大呀？！这里继续做一个假设：5, 6,-2, -3,-1, -7,8, 9 明显最大的子序列是8,9，中间跨度的那些负数都不应该加起来，这样的想法的确是对的，但是这个算法也做到了啊。 加和5,6后前面得到的最大的MaxSum一直都是11，而ThisSum才会减少，加上-7时ThisSum会变成-2，此时ThisSum会被修正为0，MaxSum没有改变还是11；接下来ThisSum加上8,9得到的ThisSum是17，要比之前的MaxSum大，所以MaxSum也被替换成17了。

这些说明都比较粗糙，见谅！