算法分析-最大子数组和

刚做了乘积最大子数组，现在趁热打铁继续研究：最大子数组和

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。

理解上一题之后，再看这道题就简单了。 不用担心负号会直接将结果反转，所以不用记录下最小的值。 只需要当前面的子串之和已经是负数时，就截断子串，由当前值重新开一个子串即可。

def maxSubArray(self, nums: list[int]) -> int:
    result = float("-inf")
    cur_max = 0
    for n in nums:
        cur_max = max(cur_max + n, n)
        result = max(result, cur_max)
    return result

示例拆解

光说概念有些抽象，现在我将拆解一个例子来说明这个过程中发生了什么，它的内部是怎样运作的。

以 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例：

我们需要找到一个子串，它的和是最大的。我们不断变动这个子串，将它的和保存到一个变量中，这个变量的初始值设置为无穷小 float("-inf")。子串的和比这个变量大，那么覆盖这个变量，比这个变量小的就不用记录了。

我们从头开始遍历：

当前值为 -2 的时候，只有一个子串 [-2]，和最大的子串就是 [-2]，和为 -2。 当前子串：[-2] 最大子串：[-2] cur_max = max(0 + -2, -2) = -2 result = max(float("-inf"), -2) = -2

当前值为 1 的时候，将它加入到我们正在研究的子串中，变成了 [-2,1]。对于 1 来说，前面的 -2 是累赘。不管后面有什么数加入这个子串，-2 只会让总和小 2。所以我们从此处截断，只保留 [1]。 这就是我们要对比子串和当前这个数的大小的原因，如果当前数与前面的子串加起来反而更小了，那么当前数不如单干。 反过来，如果当前数是负数，把子串的和拖小了，那它也没资格说话——但为了和后面的新同事保持连续，团队只能先忍着它。 所以我们的子串截断后变成了 [1]，它的和是 1。 [-2,1] 这个区间里和最大的子串就是 [1]，和为 1。 当前子串：[1] cur_max = max(-2 + 1, 1) = 1 最大子串：[1] result = max(-2, 1) = 1

当前值为 -3 的时候，我们的子串变成了 [1,-3]。 对于 -3 来说，前面的 1 是有用的，留着。不管后面有什么数加入子串，这个 1 的存在都会让其大 1，故 -3 不能单干，要抱紧 1 的大腿。 而 1 因为 -3 的加入影响了团队的水平，但是团队还在招兵买马，它只希望后面来一个大佬，能弥补 -3 拉低的水平。 我们知道 [-2,1,-3] 区间里和最大的子串就还是 [1]，和为 1。 当前子串：[1,-3] cur_max = max(1 + -3, -3) = -2 最大子串：[1] result = max(1, -2) = 1

当前值为 4 的时候，我们的子串变成了 [1,-3,4]。 1 期盼已久的大佬终于来了，但是 4 的实力远远超过它俩，根本看不上它们这个小团队。 对于 4 来说，前面的 [1,-3] 已成累赘，带着两个拖油瓶不如自己轻装上阵，于是团队将两位老成员裁撤掉了，只留下了 4。 因为 4 的到来，[-2,1,-3,4] 这个区间里和最大的子串就变成了 [4]，和为 4。 当前子串：[4] cur_max = max(-2 + 4, 4) = 4 最大子串：[4] result = max(1, 4) = 4

当前值为 -1 的时候，将 -1 加到我们正在计算的子串中 [4,-1]，来了个小卡乐咪，不影响大局，继续招人。 现在的团队变成了 [4,-1] [-2,1,-3,4,-1] 区间里和最大的子串还是 [4]，和为 4。因为 [4] 的水平很高，不过现在它招到一个 -1 后，两人组成的团队的水平变成了 3（cur_max） 当前子串：[4,-1] cur_max = max(4 + -1, -1) = 3 最大子串：[4] result = max(4, 3) = 4

当前值为 2 的时候，团队变成了 [4,-1,2]，2 就是 4 要找的人才。团队的水平增加了，并且超出了 4 的个人能力。 现在它们是 [-2,1,-3,4,-1,2] 这个区间里的最强团队了（和最大的子串）。 当前子串：[4,-1,2] cur_max = max(3 + 2, 2) = 5 最大子串：[4,-1,2] result = max(4, 5) = 5

当前值为 1 的时候，团队变成了 [4,-1,2,1]。又来了一员得力干将，团队实力继续增加，队伍里一片欣欣向荣。 当前子串：[4,-1,2,1] cur_max = max(5 + 1, 1) = 6 最大子串：[4,-1,2,1] result = max(5, 6) = 6

当前值为 -5 的时候，好景不长，不小心招到了一个大坑，一个人能拖几个人的大腿，团队水平急速下降。现在的团队变成了 [4,-1,2,1,-5] 当前子串：[4,-1,2,1,-5] cur_max = max(6 + -5, -5) = 1 最大子串：[4,-1,2,1] result = max(6, 1) = 6

当前值为 4 的时候，团队成员变成了 [4,-1,2,1,-5,4]，总算是补上了一些团队水平。但是后续已经无人可招。团队的辉煌只剩下了那张在桌上写着最强团队的合影，上面的四个身影为 [4,-1,2,1]。 当前子串：[4,-1,2,1,-5,4] cur_max = max(1 + 4, 4) = 5 最大子串：[4,-1,2,1] result = max(6, 5) = 6

至此，我们就知道了这个例子的结果。不管后续再如何扩招团队，维系团队的逻辑也还是不变的： 新来的怕团队影响自己水平，在此处没有发展。老成员又怕新来的水平太高，自己的老团队被裁撤掉。

核心的逻辑就是： 当一个团队已经会给新成员拖后腿的时候，立即舍去这个团队，由新成员上位继续带领新团队。 反之只有一种情况，新成员需要抱这个团队大腿，舍弃团队自己单干永远也达不到最高水平。

所以： 在 n 处时，如果前面的子串之和 cur_max 与 n 之和比 n 还小，那么 cur_max = n，子串从 n 继续向后增加。result 始终将最大的 cur_max 记录下来。

时间 $O(n)$：一趟遍历，每轮都是常数次比较和加法。

空间 $O(1)$：只维护 cur_max、result 两个变量，不随 n 增长。

总结

最开始我陷入了一个思维误区，总想把所有元素能组成的子串都枚举一遍，却忽略了一个关键前提：我们只关心最大。这恰恰是动态规划能成立的根本——问题具有最优子结构。

定义状态：dp[i] 表示以第 i 个元素结尾的、和最大的连续子数组的和。有了这个定义，答案就是所有 dp[i] 里的最大值。

状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])

它只有两个决策：若 dp[i-1] > 0，前一个状态是正增益，就接过来（dp[i-1] + nums[i]）；若 dp[i-1] <= 0，前一个状态成了负累赘，就丢弃，从当前元素重新起头（nums[i]）。这就是"前缀和为负就截断"的由来。

注意 dp[i-1] 的正负，和 nums[i-1] 的正负是两回事：即使 nums[i-1] 是负数，它前面也可能累积了一段很大的正前缀，让 dp[i-1] 仍是正的，这时照样要接上。前缀既可以是一个元素，也可以是一整段子数组。

这个转移只依赖 dp[i-1] 一个状态，不关心更久远的历史，这种性质叫无后效性。正因如此，代码里用滚动变量 cur_max 代替整个 dp 数组，空间就从 $O(n)$ 压到 $O(1)$，这就是滚动数组优化。

把视角拔高：这类"找最 x 的子串"问题，本质都是维护一个"以当前位置结尾"的最优状态，每步按转移方程做决策，剔除会拖累最终目标的因素。最大子数组和里，负前缀是拖累因素，为负就截断；乘积最大子数组里，0 是拖累因素，遇到就截断，而负数因负负得正不是拖累因素，反而要同时保留最大、最小两个状态来应对翻转。