精秒的算法──最大子序列和

给定（可能为负）的整数序列 A，求它的子序列能达到的最大值。例如对于 [-2, 11, -4, 13, -5, -2] 这个序列，答案为 20 （选取子序列 [11, -4, 13] ）。方便起见，如果所有数都是负数，则认为最大的子序列和为 0。

这个问题十分有趣，它有至少 4 种不同的解法，每种方法的时间复杂度各不相同。

(本文内容可在《数据结构与算法分析》一书中找到，本文算是读书笔记)

解法一

看到题目先审题，我们逐个分析：

1. 子序列，即从序列的 N 个元素中任意选 i , j 分别作为起始和结束，即 $A_i, A_{i+1}, \dots A_j$ 这个序列
2. 子序列和：即 $\sum_{k=i}^j{A_k}$。

因此要求子序列和，很自然地，我们写出下面的代码：

def solution1(A):
    max_sum = 0
    for i in range(len(A)):
        for j in range(i, len(A)):
            max_sum = max(max_sum, sum(A[i:j+1]))
    return max_sum

solution1([-2, 11, -4, 13, -5, -2]) # => 20

上面的代码跟我们的思路完全一致，先穷举所有的 i, j 组合，对每个组合计算子序列和，并取最大值。

我们知道， i, j 的组合有 $C_n^2 = O(n^2)$ 个，且每次计算子序列和需要 $O(n)$，算法的复杂度是 $O(n^3)$。这个复杂度是很可怕的，如果序列里有 10 万个数就基本算不出结果了。

解法二

优化算法时需要思考的是，原算法是不是有“重复计算”？减少这些重复计算就能提高算法的效率。

对于解法一而言，在计算子序列和时，其实做了不少的重复计算，如下：

计算 i=3, j=4 的序列和时，重复计算了 i=3, j=3 的序列和。我们利用这一发现来提供算法的效率：

def solution2(A):
    max_sum = 0
    for i in range(len(A)):
        this_sum = 0
        for j in range(i, len(A)):
            this_sum += A[j]                 # 只增加当前的值，减少重复计算
            max_sum = max(max_sum, this_sum)
    return max_sum

solution2([-2, 11, -4, 13, -5, -2]) # => 20

这个解法的时间复杂度是 $O(N^2)$，对于 10 万的数据量已经能算出结果了，虽然比较慢。

解法三

上面的算法里还有不必要的计算：假设我们通过一些对比，已经知道了三个信息：

1. 所有包含 x 元素的子序列的和的最大值
2. 所有元素均在 x 之前的子序列的和的最大值
3. 所有元素均在 x 之后的子序列的和的最大值

则其实我们要求的结果就是这三个值的最大值。上图中，我们不会去计算和对比子序列 [i, m] 的值，因为它也包含 x 元素，所以必然小于 [i, n] 。因此减少了一些不必要的计算。代码如下：

def solution3(A):
    # 基准情形
    if len(A) == 0:
        return 0
    elif len(A) == 1:
        return max(0, A[0])

    mid = len(A)//2
    left_part = A[:mid]
    right_part = A[mid:]

    max_left_sum = solution3(left_part)
    max_right_sum = solution3(right_part)

    # 计算包含 mid 的子序列和的最大值
    # = 以 mid 结尾的子序列的和的最大值 + 以 mid+1 开头的子序列的和的最大值

    max_left_border_sum = 0
    left_sum = 0
    for v in reversed(left_part):
        left_sum += v
        max_left_border_sum = max(left_sum, max_left_border_sum)

    max_right_border_sum = 0
    right_sum = 0
    for v in right_part:
        right_sum += v
        max_right_border_sum = max(right_sum, max_right_border_sum)

    return max(max_left_sum, max_right_sum, max_left_border_sum + max_right_border_sum)

solution3([-2, 11, -4, 13, -5, -2]) # => 20
solution3([4, -3, 5, -2, -1, 2, 6, -2]) # => 11

该解法的时间复杂度为 $O(N\log N)$。计算法复杂度为 $T(N)$，则依据代码我们有

$$ \begin{align} T(1) &= 1 \\ T(N) &= 2T(N/2) + O(N) \end{align} $$

可以最终推出 $T(N) = O(N \log N)$。这个复杂度对于 10 万的数据量可以轻松得到结果，甚至对于 100 万的数据量也能很快得到结果。

解法四

通常情况下，得到一个 $O(N \log N)$ 的算法已经能应付绝大多数现实情况下的问题了。但难以置信的是，对于这个问题而言，算法还可以继续优化。代码如下：

def solution4(A):
    max_sum = 0
    this_sum = 0
    for x in A:
        this_sum += x
        if this_sum > max_sum:
            max_sum = this_sum
        elif this_sum < 0:
            this_sum = 0
    return max_sum
solution4([-2, 11, -4, 13, -5, -2]) # => 20

这个方法比起上一个算法减少了哪些不必要的计算？考虑下面的示例：

解法三在计算包含中间元素的子序列的最大值时，会向左求和，直到 -2 为止。但之后在求左边元素的子序列最大值时，又要重复计算 -2, -3 的和，尽管我们已经知道最大和的子序列肯定不会以 -2 开头。

马后炮地说，上面这个算法性能代码简洁，性能又高，是因为我们充分分析了问题的特点，注意到：

1. 注意到我们只需要知道最大的子序列和，并不关心具体是哪个子序列得到了最大值。
2. 如果 A[i] 为负数，则最大和肯定不会以它为起点
3. 类似的，如果一个子序列的和为负数，则它不会是最大和子序列的前缀。

因此当累加和得到负数时，我们可以立马抛弃它，而不需要再考虑这个子序列与后续子序列的组合。

这个算法是 $O(N)$，几乎是你能得到的最好的复杂度。

小结

不得不承认，我在思考这个题目的时候怎么也想不出来解法三和解法四。还是对题目的分析不够透彻，对题目的隐含条件挖掘得不够深入。而对我的启示则是：复杂度的提升根本在于减少不必要的计算，而这依赖于问题/输入本身的约束。就像通过两两对比的排序理论的最好复杂度是 $O(N \log N)$，而桶排序却可以通过其它的约束达到 $O(N)$。