KT学算法（一）——数列连续子列最大和有关问题的O(n)解法

深刻意识到算法的重要性。从头开始，积累基本的算法模型。

问题描述

数列连续子列最大和问题是指：给定一个数列A，求出一个子数列，{Ai,Ai+1,Ai+2，……，Aj}，其中i<=j，使得这个子数列中每一个元素的和最大。

举例说明

盗用别人一个例子：

给定整数序列：{0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5}
其中和最大的连续子数列为：{21, 8, -9, 10, -1, 3, 6, 5}

问题分析

显然如果数列A中的每个元素非负，那么数列A本身，作为它自己最大的子数列，就是我们要求的具有最大和的子数列。因为此时Sn单调不减。

如果数列A中最后一个数为负数，显然具有最大和的子列为{A1,A2,……，An-1}。

但是如果数列A如前例所示，混有多个负数，答案就不再显然了。

说了这么多废话，其实只是想表达一个意思，和简单的从A1开始遍历，将每个元素放入子数列中相比，将会遇到的最大的麻烦在于一个负数Ai的出现，打断了子数列的不断扩张，而且最要命的是此时并不清楚这个Ai是否意味着子数列扩张的只是被临时暂停（比如Ai = -1但Ai+1 = 5），还是永久暂停（比如Ai之后的数都为负数）。而且似乎并没有一个好的方法处理这个临时的负数Ai。

理论基础

这里必须引出一个基本定理：

记S（Ai,Aj）= Ai + Ai+1 + …… + Aj。（i <= j）
对于任意的x,y,z 满足x < y < z，如果有S(Ax,Ay) < 0，则S（Ax,Az）不是最大的连续子列和。

这个结论非常好证明，因为显然S（Ay+1,Az）> S（Ax,Az）。
但是这个结论告诉我们如果出现某一子数列的和小于0，那么可以跳过此子列，从这个子列最后一项的下一项开始寻找即可。

解题思路

经过以上分析，大致可以想到，这个算法是一个线性算法。我们维护一个动态的子列，对于遍历的每一个元素，都放入子列中去，也就是说子列一直在扩张，但是一旦当前子列的和为0，那么子列立刻会被清零（原理如上所说）。因此，这个动态子列并不是我们最终求出的子列，我们不仅需要一个变量来标记子列的开始位置，在合适的时候清空这个子列，还需要一个变量来标记子列的结束位置。当然，这里所指的维护，仅仅是指记录子列的起始位置和终止位置，并不是实际的存储数组中的元素。

如何解决遇到负数的问题呢？

答案是我们并不理会这个负数，而是继续前进，往后寻找。因为这个在负数之后还有可能遇到绝对值更大的正数。但是一旦目前这个子列的和小于0，那么直到我们维护的子列的最后一个元素都作废了。如果始终不出现子列和小于0的情况，这个子列会不断扩展，但是标记真正要求的最大和子列的结束位置并不是随时变化的，只有在当前子列最大和大于此前最大和的时候才会有更新（这里用到贪心的思想）。

经过分析，我们再次明确了另外两个变量。一个用于记录当前子列和，另一个用于记录此前的子列最大和。

再看一下给的数据{0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5}

当遍历到-3的时候，我们维护的子列是{0，-3}，、、遍历到8的时候，维护的子列是{0, -3, 6, 8}，而遍历到了-20的时候，维护的子列就被清空了。所谓的清空仅仅是指，子列和被置为0，而最大和子列的结束位置不应该发生任何变化。当遍历到21的时候，因为现在的子列和（原子列和+21）>原最大子列和，所以最大和子列的结束位置变为5。形象的说，在最大和子列的结束位置到动态子列的结束位置之间这一段，类似于缓存，可以被舍弃，也可以被纳入最大和子列中。

还有一个比较tricky的是，最大和子列的初始位置并不能像结束位置一样被保存并适时更新。比如说遇到20的时候，最大和子列的初始位置应该变为几呢？无论怎么处理都有可能导致bug，所以如果需要输出初始位置的话，应该在循环结束之后由最大和以及结束位置倒推出初始位置。

代码实现

int main(int argc, const char * argv[]) {
    int a[] = {0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5};

    int endPos = 0;
    int maxSum = 0;
    int currentSum = 0;

    for (int i = 0; i < 13; i++) {
        if (currentSum + a[i] > maxSum) {
            //如果当前维护的子列和加上新的这个元素大于原来的最大子列和
            currentSum += a[i];//更新当前子列和
            maxSum = currentSum;//更新最大子列和（贪心）
            endPos = i;//更新最大和子列的结束位置
        }
        else{
            //并没有比原来大，加入“缓存区域”
            if (currentSum + a[i] >= 0) {
                currentSum += a[i];//仅仅更新当前子列和即可
            }
            else{
                //当前子列和小于0，这个子列作废，当前子列和置零
                currentSum = 0;
            }
        }
    }

    //倒推最大和子列的初始位置
    int tempMax = maxSum;
    int beginPos = endPos;
    while (tempMax > 0) {
        tempMax = tempMax - a[beginPos];
        beginPos --;
    }
    beginPos ++;//多减了一次，把最后一次减的补上
    printf("max sum is %d\n",maxSum);
    printf("a[%d] = %d\n",beginPos,a[beginPos]);
    printf("a[%d] = %d\n",endPos,a[endPos]);
    return 0;
}

总结

本质上还是贪心，只是在贪心的过程中，会对比较对象（当前子列和）做动态的调整。