最大子序列和问题

最大子序列和问题乃经典算法问题之一，很多教科书和技术文章都对此有详述，博主重新整理一遍乃是为了消化和日后翻阅，不喜勿喷。

问题描述

---

给定一个整数数组，求出这组数字子序列和的最大值（为简单起见，若数组中所有数字都为负数，则返回0）。例如：

序列：-2 11 -4 13 -5 -2，则最大子序列和为20。

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。

算法一

---

//穷举法，所有的组合都加一遍，得到最大值
int GetMaxSubsequenceSum1(int[] array)
{
    int tempSum = 0, maxSum = 0, i, j, k;
    for (i = 0; i < array.Length; i++)
    {
        for (j = i; j < array.Length; j++)
        {
            tempSum = 0;
            for (k = i; k < j; k++)//当j++后，已得到的原j个数字的和又要重新计算获取——在算法2中避免了这步重复计算的问题
                tempSum += array[k];
            if (tempSum > maxSum)
                maxSum = tempSum;
        }
    }
    return maxSum;
}

这是一个O(N³)的算法，算法本身很容易理解，而且很直观的感觉做了很多无用操作。例如：i = 0, j = 3时，会计算a[0] + a[1] +…+ a[3]；而当i = 0, j = 4时候又会计算a[0] + a[1] +…a[4]。算法二会对此做一改进。（有句“格言”：计算任何事情不要超过一次。）

算法二

---

 1 int GetMaxSubsequenceSum2(int[] array)
{
    int tempSum = 0, maxSum = 0, i, j;
    for (i = 0; i < array.Length; i++)
    {
        tempSum = 0;
        for (j = i; j < array.Length; j++)
        {
            tempSum += array[j];//tempSum存储前j个数的和
            if (tempSum > maxSum)
                maxSum = tempSum;
        }
    }
    return maxSum;
}

比算法一少了一层for循环，so，复杂度也降为O(N²)。在日常工作中，做到这步我就满足了，几乎不会去想是否还有（时间上）更优的方法。

算法三

---

 1 //分治策略（divide-and-conquer）
int GetMaxSubsequenceSum3(int[] array, int left, int right)
{
    if (left == right)//此时可判定只有一个元素
        return array[left] < 0 ? 0 : array[left];//若是负数则返回0

    int center = (left + right) / 2;
    int maxLeftSum = GetMaxSubsequenceSum3(array, left, center);
    int maxRightSum = GetMaxSubsequenceSum3(array, center + 1, right);

    //求出以左边对后一个数字结尾的序列最大值 
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i >= left; i--)
    {
        leftBorderSum += array[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }

    //求出以右边对后一个数字结尾的序列最大值 
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int j = center + 1; j <= right; j++)
    {
        rightBorderSum += array[j];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }

    return Math.Max(Math.Max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBorderSum);
}

所谓分治策略，将大的问题分成大致相等的若干子问题，对它们求解并合并为最终解，依靠的即是递归算法。具体到上述算法，复杂度为O(NlogN)（猜测NlogN中的系数N乃是第8、9行两次递归运算带出来的）。分析算法最让人困惑的大概就是对数的出现。除分治算法外，可将对数常出现的规律概括为以下一般法则：如果一个算法用常数时间（O(1)）将问题的大小削减为其一部分（通常是二分之一），那么该算法的复杂度就是O(logN)。另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是O(N)的。那么，是否还有更优的（时间上）算法呢？

算法四

---

 1 int GetMaxSubsequenceSum4(int[] array)
{
    int tempSum = 0, maxSum = 0;
    for (int j = 0; j < array.Length; j++)
    {
        tempSum += array[j];
        if (tempSum > maxSum)
            maxSum = tempSum;
        else if (tempSum < 0)
            tempSum = 0;
    }
    return maxSum; 
}

很容易理解上述代码的时间复杂度是O(N)，但是要是弄明白为什么正确就比较费力了。其实这个是算法二的一个改进。分析的时候也是i代表当前序列的起点，j代表当前序列的终点。如果我们不需要知道最佳子序列的位置，那么i就可以优化掉。

重点的一个思想是：如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优子序列的前缀。例如说，循环中我们检测到从a[i]到a[j]的子序列是负数，那么我们就可以推进i。关键的结论是我们不仅可以把i推进到i+1，而且我们实际可以把它一直推进到j+1（j是使得从下标i开始成为负数的第一个下标）。举例来说，令p是i+1到j之间的任何一个下标，由于前面假设了a[i]+…+a[j]是负数，则开始于下标p的任意子序列都不会大于在下标i并且包含从a[i]到a[p-1]的子序列对应的子序列。因此，把i推进到j+1是安全的，不会错过最优解。注意的是：虽然，如果有以a[j]结尾的某序列和是负数就表明了这个序列中的任何一个数不可能是与a[j]后面的数形成的最大子序列的开头，但是并不表明a[j]前面的某个序列就不是最大序列，也就是说不能确定最大子序列在a[j]前还是a[j]后，即最大子序列位置不能求出。但是能确保maxSum的值是当前最大的子序列和。这个算法还有一个有点就是，它只对数据进行一次扫描，一旦a[j]被读入处理就不需要再记忆。它是一个联机算法。

联机算法：在任意时刻算法都能够对它已读入的数据给出当前数据的解。

常量空间线性时间的联机算法几乎是完美的算法。

其它

---

关于算法三中提到的对数复杂度，除分治算法外，还有对分查找（已排序集合）、欧几里得算法（查找最大公约数）、幂运算等，都有该特点。

时间复杂度比较（由小到大）：O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(2ⁿ) < O(N!) ，这有点数学常识的一眼就能比较出来。

参考资料：

最大子序列和问题

数据结构与算法分析——C语言描述第二版（美 Mark Allen Weiss著  冯舜玺 译）第2章