给定整数序列 A，对所有的子序列分别求和，求和能达到的最大值。例如对于 [-2, 11, -4, 13, -5, -2] 这个序列，答案为 20 (选取子序列 [11, -4, 13])。这个问题十分有趣，它有至少 4 种不同的解法，每种方法的时间复杂度各不相同。

方便起见，如果所有数都是负数，则认为最大的子序列和为 0。

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

解法一

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

1. 什么是子序列？任选 i, j 分别作为起始和结束，取元素 $A_i, A_{i+1}, \dots A_j$ 形成子序列
2. 子序列和：即 $A_i + A_{i+1} + \dots + A_j$。

要求子序列和的最大值，只需要穷举出所有的子序列，求和并比较即可。于是代码如下：

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 大约有 $\frac{C_n^2}{2} = O(n^2)$ 个，且每次计算子序列和需要 $O(n)$，算法的复杂度是 $O(n^3)$。这个复杂度很可怕，如果序列里有 10 万个数就基本算不出结果了。

解法二

优化算法时需要思考的是，原算法是不是有“不必要的计算”？减少这些计算就能提高算法的效率。对于解法一而言，在计算子序列和时，其实做了不少的重复计算，如下：

计算 i=1, j=4 的序列和时，重复计算了 i=1, 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)$。