关于最大子段和线性算法的证明

重复题目:

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

此题最初载于

http://blog.csdn.net/v_JULY_v/article/details/6444021

我在文章中也对其做了总结，并对线性时间的算法做了自己的证明，这里重复如下（其实后面的递归式本身就证明了算法的正确性，这里只是希望通过暴力的方法尝试对从另一个方面对它进行证明，即穷举所有可能出现情况）：

“

关于这道题的证明，我的思路是去证明这样的扫描法包含了所有n^2种情况，即所有未显示列出的子数组都可以在本题的扫描过程中被抛弃。

1 首先，假设算法扫描到某个地方时，始终未出现加和小于等于0的情况。

我们可以把所有子数组（实际上为当前扫描过的元素所组成的子数组）列为三种：

1.1 以开头元素为开头，结尾为任一的子数组

1.2 以结尾元素为结尾，开头为任一的子数组

1.3 开头和结尾都不等于当前开头结尾的所有子数组

1.1由于遍历过程中已经扫描，所以算法已经考虑了。1.2确实没考虑，但我们随便找到1.2中的某一个数组，可知，从开头元素到这个1.2中的数 组的加和大于0（因为如果小于0就说明扫描过程中遇到小于0的情况，不包括在大前提1之内），那么这个和一定小于从开头到这个1.2数组结尾的和。故此种 情况可舍弃

1.3 可以以1.2同样的方法证明，因为我们的结尾已经列举了所有的情况，那么每一种情况和1.2是相同的，故也可以舍弃。

2 如果当前加和出现小于等于0的情况，且是第一次出现，可知前面所有的情况加和都不为0

一个很直观的结论是，如果子段和小于0，我们可以抛弃，但问题是是不是他的所有以此子段结尾为结尾而开头任意的子段也需要抛弃呢？

答案是肯定的。因为以此子段开头为开头而结尾任意的子段加和都大于0（情况2的前提），所以这些子段的和是小于当前子段的，也就是小于0的，对于后面也是需要抛弃的。也就是说，所有以之前的所有元素为开头而以当前结尾之后元素为结尾的数组都可以抛弃了。

而对于后面抛弃后的数组，则可以同样递归地用1 2两个大情况进行分析，于是得证。

这个算法的证明有些复杂，现在感觉应该不会错，至少思路是对的，谁帮着在表达上优化下吧。:-)

”

后来在《编程珠玑》中看到了对此种算法的解释，实际上，编程珠玑中对于sum小于0后舍弃的定义如下：

maxendinghere = max(maxendinghere, 0)

这里的maxendinghere就是网上常见算法的sum，其意义是以当前元素为结尾的最长字段的长度。

我们可以看到，这其实是一个动态规划解法，最优子结构可以归纳为：

　　s[0] = max(a[0], 0)

　　s[i] = max(s[i - 1] + a[i], 0)

即如果当前元素加上以前一个元素为结尾的子段和小于0，就把以当前元素为结尾的子段和设为0。实际上这个“子段”是一个空段。我不知道为什么非要区分0和非零，可能是在这道题里“小于0的元素会让整个子段值变小”这个概念很显眼吧，但是这种情况确实忽略如果所有输入为负数的情况，虽然题目假设输入有正有负。

于是我试图改变最优子结构的构造，抛弃0的概念，定义为：

　　s[0] = a[0]

　　s[i] = max(s[i - 1] + a[i], a[i])

这样看起来比较直观，而且“以元素a[i]为结尾的最大子段和”就不会是一个空子段了。

这种规划方法我不知道是否有什么错误，看起来没什么问题，我实现了一下：

#include <iostream>

using namespace std;

#define MAX_LEN 100

template<class T>
void maxSubArr(T *arr, int len, int &start, int &end, T &max_sum)
{
    if(len <= 0)
        return;

    T max_ending_sum;
    int i, starts[MAX_LEN]/*the start of the max sub array end with a[i]*/;

    max_ending_sum = arr[0];
    max_sum = arr[0];
    start = 0;
    end = 0;
    starts[0] = 0;
    for(i = 1; i < len; i ++)
    {
        // max_ending_sum here refers to the maximum subarray length ends with element a[i - 1]
        if(max_ending_sum + arr[i] > arr[i])
        {
            max_ending_sum = max_ending_sum + arr[i];
            starts[i] = starts[i - 1];
        }
        else
        {
            max_ending_sum = arr[i];
            starts[i] = i;
        }

        // max_ending_sum now refers to the maximum subarray length ends with element a[i]
        if(max_ending_sum > max_sum)
        {
            max_sum = max_ending_sum;
            start = starts[i];
            end = i;
        }
    }
}

int main()
{
    int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
    int len = 8;
    //int a[] = {-1, -2, -3, -10, -4, -7, -2, -5};
    //int len = 8;
    int start, end, max_sum, i;

    maxSubArr(a, len, start, end, max_sum);

    cout << "maximum summary : " << max_sum << endl;
    cout << "the subarray : ";
    for(i = start; i <= end; i ++)
    {
        cout << a[i] << " ";
    }
}

输出为：

maximum summary : 18
the subarray : 3 10 -4 7 2

特别的，当输入变为：

int a[] = {-1, -2, -3, -10, -4, -7, -2, -5};

全部为负时，这个算法不用特殊考虑就可以得出正确结果：

maximum summary : -1
the subarray : -1

看起来没什么错~