0053 - Maximum Subarray

Algorithm

August 18, 2023

前言

这篇的重点在于讲述从启发式算法到对 Kadane算法的独立再发现的过程。

难度定位

对于 LeetCode 来说，本题的定位在 Medium 难度，只能说这是一个令人不满意的折中的结果。

首先这实在是一道太经典的题目，有很简单的解决方法，对于那些接触过它的人来说，只需要不到一分钟的时间就能写完，从这个角度上说，可以直接定位在 Easy 。

但对于那些并没有正式接触过的人来说，就题论题，从输入的数据规模来看，这道题的难度是非常高的，对于运行时语言来说，实际上只有 $O(n)$ 的解法能过，而且还必须是不太慢的 $O(n)$ 解法，而其他类似类型题目，通常 $O(n^2)$ 就能过，但从这一点，这就一定是 Hard 难度的题目。

总地来说，我们没有任何理由去假设用户的学习履历，而这道题本身就是一道 Hard 难度的题目，因此它定位就应该在 Hard 。

题干

问题描述

破题

源代码

求一个数组的最大值子序列。

首先可以想到分段树上有一个经典应用，就是计算最大子段和，这个时间复杂度是最优的，但一定不是最快的，在纯运行时语言里，这种复杂数据结构的表现都不会太好，因为本来可以忽略掉的无关操作都对时间有显著地影响。

何况这种方法写起来也不是很简单，因此先把这种方法放到最后，作为比较。

解⓪简单DP：TLE：

最简单地记录两头索引的 DP，用前缀和数组 $O(1)$ 地计算区间和，时间复杂度为 $O(n^2)$ ，即使做了很多优化，比如压缩数组，排除负数（需要处理全是负数的情况），也仍然过不了关。

from typing import List
from itertools import accumulate


def solve(nums: List[int]) -> int:
    max_v = max(nums)

    if max_v <= 0:
        return max_v

    nums = compress(nums)
    n = len(nums)

    pref_sum = list(accumulate(nums))
    ans = max(pref_sum)

    for i in range(1, n):
        if nums[i] < 0:
            continue
        for j in range(i, n):
            ans = max(ans, pref_sum[j]-pref_sum[i-1])

    return ans

def compress(nums: List[int]) -> List[int]:
    n = len(nums)

    nums2 = []

    i = 0

    while i < n:
        acc = 0

        if nums[i] >= 0:
            while i < n and nums[i] >= 0:
                acc += nums[i]
                i += 1
        else:
            while i < n and nums[i] < 0:
                acc += nums[i]
                i += 1

        nums2.append(acc)

    return nums2

解①启发式算法：

这一节是本篇的重点，讲述我个人如何一步步从一个直觉地和局部经验地算法设计出本质上就是 Kadane 算法的过程。

1. 观察：

最大子段和如果都是正数，那么整个数组的和就是最大子段和，这个题目就没有意义了，一定是有负数才让问题具有复杂性，当然如果全都是负数那么问题也很简单，就是最大的那一个单个负数（或者说绝对值最小的那个负数），而更多地应该是正数和负数混合的情况（零总是可以被简单忽略掉）。

这样地话，排除全负数地情况后考虑，如果数组结尾的的数字是非正数，那么它可以直接被忽略掉；但如果结尾是正数，那就要看它后面可能存在的来自负数的减益与来自正数的增益哪一个更大。

为了考虑方便和编写代码，可以就像前面算法一样对数组进行压缩：compress，合并临近的正值和非正值，这样总是可以得到一个正负相间的数组。

在这个基础上考虑什么时候能够保留结尾的正数呢？就是正数邻接的负数的绝对值小于这个正数，这样正负加起来一定对最大和有增益。反之，如果正负加起来小于等于零，那么显然这一段儿就可以被扔掉，因为没有任何增益。

2. 问题：

那么如果一个正负组之后还有一个正负组该怎么样呢：

如果那个正负组仍然是非负收益，那么仍然可以保留；
可是如果是负收益，又该如何判断是否该保留呢？

试着考虑在数组的另一端也如此处理来压缩问题规模，但是这样仍然会遇到一个正收益的正负组后面的一个负收益的正负组问题。

3. 解决方法：

看来不得不正面考虑正收益的正负组后面的出现负收益的正负组的问题，考虑直接合并我们遇到的正负组，就像我们压缩数组一样，如果是正收益就保留，如果是非负收益就抛弃，这样好像问题就解决了！

4. 观察：

这样如果从两边开始一层层剥掉两头的正负组，是不是问题就能在 $O(n)$ 的时间内解决？！我们现在好像已经从对问题局部的优化开始，窥得了最优解的思路。我自己就把这个思路称为“洋葱变换”（Onion Transform）

像这样剥下去，最后应该得到：

一个“去核”洋葱，也就是剥到最后，发现里面什么都没有；
或者带芯儿洋葱，最后剩下一个孤正数，因为前面都是正负组，而整个压缩后的数组是正负相间的。

这样好像只要计算最后剩下的皮加上可能存在的芯的值，就能得到整个数组的最大子序列和。

5. 问题：

但是，两头剥洋葱实际还有第三种情况，就是这根本是个“假洋葱”（Fake Onion），剥到最后发现里面剩一个负数，这应该是不存在的情况，但就是发生了，因为两头的正负组存在重叠，这样我们就不能正确计算了。

6. 解决方法：

由于存在负芯儿的“假洋葱”，不能从两头剥，考虑直接从一头剥，这样肯定就不会出现正负组重叠的情况。

7. 观察：

但这样好像就得到了一个未曾设想的局面：一段段儿由负数隔开的正值的最大子序列，也就是说在压缩正负组的过程就可以计算得到最大子序和。

至此为止我们得到了一个可运行的算法：

def solve(nums: List[int]) -> int:
    max_v = max(nums)

    if max_v <= 0:
        return max_v

    nums = compress(nums)
    max_unit = max(nums)  # get max unit

    # Onion Transform

    max_seq = 0

    while len(nums) >= 3:
        if nums[-1] <= 0:
            nums.pop()
        else:
            layer = nums.pop() + nums.pop()

            if layer > 0:
                nums[-1] += layer

            max_seq = max(max_seq, nums[-1])

    max_seq = max(max_seq, sum(nums))

    return max(max_unit, max_seq)

时间复杂度 $O(n)$ 。

运行时间：622 ms (beats 74.97%)，内存占用：30.42 MB (beats 83.1%) 。

（后来发现这个运行时间已经相当好了）

8. 思路推广：

这个算法应该有更简洁、更一般化地表示，不需要数组压缩、也不必考虑正负组，只要能带来非负收益，就可以进行压缩。

9. 思路推广：

使用一个追踪边的累积变量 acc，用它来代替对输入的边缘点的修改，同时也不需要直接检测收益是否为负，先计算加和，取它与新的边缘点的最大值。

这样可以得到一个非常简洁地形式：

def solve(nums: List[int]) -> int:
    return max(accumulate(nums, lambda x, y: max(y, x+y)))

总是使用前一个计算的值作为状态，也就是 x ，y 是当前的边缘点

这个版本并不是我写的，因为它使用 itertools 里面的工具虽然让代码看起来很简单，但根据以往经验，我就知道这个性能表现¹并不怎么样，实际果然如此：

时间复杂度 $O(n)$ 。

运行时间：592 ms (beats 87.39%)，内存占用：30.56 MB (beats 51.70%) 。

运行时间相比前一个朴素版本不仅提升有限，内存占用甚至还更多了！足可见 itertools 有非常大的优化空间。

更适合当前版本的应该是：

def solve(nums: List[int]) -> int:
    ans = acc = nums.pop()

    while nums:
        v = nums.pop()
        tmp = acc + v

        if tmp > v:
            acc = tmp
        else:
            acc = v

        if ans < acc:
            ans = acc

    return ans

时间复杂度 $O(n)$ 。

运行时间：537 ms (beats 99.80%)，内存占用：26.77 MB (beats 99.95%) 。

核心有三点：

普通循环替代 itertools
普通条件判断替代 max
预先计算一个变量也有有意义地性能提升

实在是有些无语²

与Kadane算法：

到了这一步，这可以发现，这就是 Kadane 算法做的事，我们只是独立地重新发明了它³

与其他思路：

这个最终的解决方法还可以通过 DP 或者说其他地算法思想推导得到，但总是实质一样，我并不考虑这里一定要使用什么思想来解决，就是一步步地想，如果最终要对它总结，我更愿意把它归类为在时间上进行 DP 的算法。

解②分段树：

经典地一个分段树应用的题目，因为求得是整个数组的最大子序列和，因此只需要写建树的代码即可，返回根节点的值即可。

min_value = -10 ** 4 - 1

def solve(nums: List[int]) -> int:
    tree = build(nums)

    return tree[0][-1]

def build(nums: List[int]):
    """ DFS型 """
    n = len(nums)
    data = [None] * (2*n-1)
    _build(data, nums, 0, n-1, 0)

    return data

def _build(data: List, nums: List[int], tl: int, tr: int, i: int):
    """ pref  0 # max prefix sum
        suff  1 # max suffix sum
        sum   2 # all sum
        ans   3 # max range sum
    """

    if tl == tr:
        data[i] = (nums[tl], nums[tl], nums[tl], nums[tl])
        return

    mid = (tl+tr) // 2
    sub_lf = 2*(mid-tl+1) - 1
    i_lf = i+1
    i_rh = i_lf+sub_lf

    _build(data, nums, tl, mid, i_lf)
    _build(data, nums, mid+1, tr, i_rh)

    data_lf = data[i_lf]
    data_rh = data[i_rh]

    data[i] = (
            max(data_lf[0], data_lf[2]+data_rh[0]),
            max(data_rh[1], data_rh[2]+data_lf[1]),
            data_lf[2]+data_rh[2],
            max(data_lf[3], data_rh[3], data_lf[1]+data_rh[0])
        )

时间复杂度 $O(n)$ 。

运行时间：1067 ms (beats 5.02%)，内存占用：53.78 MB (beats 6.15%) 。

同样没有使用 Python 的类，而是元组，来保存每个点的 4 个基本信息，因为类实在是太慢啦！

与其他思想

如果不从分段树地角度看，也可以直接使用分治地思想做类似地操作，但是也依赖递归，区别是我们把递归需要保存的堆栈信息显式地存储到了起来。

注解

###

至少是当前的 Python 3.10 版本 ↩
我认为从根本上讲，是原作者的观念保守，为了维持 Python 的纯解释性，从而放弃了很多更进一步地优化，并且也没有引进 JIT 的机制 ↩
可能区别是原始的 Kadane 算法面对的问题是只返回非负值，如果全都是负数就返回 $0$ ↩