系列导航：LeetCode Hot100 刷题导航（系列导航） · 上一篇：Hot100 76 | 最小覆盖子串：可变长滑动窗口的代表题 · 下一篇：Hot100 56 | 合并区间：排序后逐段吞并

这一题虽然被放在数组专题里，但很多人真正第一次“理解动态规划为什么成立”，就是从它开始的。它非常适合作为动态规划入门题，因为它的状态特别短、转移特别清楚，但里面的思维非常典型。

专栏导读

这题之所以经典，不是因为代码难，而是因为它会逼着你真正去想：

  • 当前这个位置的最优答案，和前一个位置有什么关系
  • 什么叫“以当前位置结尾的最优值”
  • 为什么这题不是单纯靠直觉贪心，而是动态规划

这篇会重点讲清楚下面几件事：

  1. 什么叫“连续子数组”
  2. 暴力法为什么天然成立
  3. 为什么可以把问题变成“以某个位置结尾的最优值”
  4. cur 和 ans 分别代表什么
  5. 为什么状态转移只有两个选择

1. 题目到底在说什么

题目给你一个整数数组 nums，要你找出：

  • 一个连续子数组
  • 这个子数组的元素和最大

最后返回这个最大和。

例如：

1
nums = [-2,1,-3,4,-1,2,1,-5,4]

答案是：

1
6

因为最大连续子数组是：

1
[4,-1,2,1]

它们的和等于：

1
6

2. 什么叫“连续子数组”

这是这题第一眼必须看懂的地方。

它要求的是：

  • 连续

所以你不能这样想：

  • 把数组里最大的几个正数挑出来相加

这在很多情况下会错，因为那些数未必挨在一起。

例如：

1
[-2, 1, -3, 4]

这里你不能直接拿：

  • 1 + 4 = 5

因为 1 和 4 中间隔着 -3，它们不能组成连续子数组。

所以这题永远在找：

  • 原数组里连续的一段

3. 先把题目翻译成人话

如果把这题翻译成最直白的话，其实就是：

  • 从数组中截出很多很多连续片段
  • 每个片段都算一遍和
  • 看哪一段最大

这已经能帮你自然想到第一种方法：暴力枚举。

4. 方法一：暴力枚举

4.1 最直观的想法

第一次做这题时，最自然的思路一定是：

  1. 枚举起点 i
  2. 再枚举终点 j
  3. 把区间 [i, j] 的和算出来
  4. 不断更新最大值

这就是最朴素的暴力法。

4.2 Python Tutor 版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def max_sub_array(nums):
    ans = nums[0]

    for i in range(len(nums)):
        total = 0

        for j in range(i, len(nums)):
            total += nums[j]
            ans = max(ans, total)

    return ans

print(max_sub_array([-2,1,-3,4,-1,2,1,-5,4]))

4.3 LeetCode 可提交版代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxSubArray(self, nums):
        ans = nums[0]

        for i in range(len(nums)):
            total = 0

            for j in range(i, len(nums)):
                total += nums[j]
                ans = max(ans, total)

        return ans

4.4 每一行代码在做什么

先看：

1
ans = nums[0]

为什么不是初始化成 0？

因为这题数组里可能全是负数。

例如：

1
[-3, -2, -5]

正确答案应该是：

1
-2

如果你把 ans 初始化成 0，就会错误地得到 0。

所以更稳的做法是：

  • 直接用数组里的第一个元素初始化

再看外层循环：

1
for i in range(len(nums)):

这里的 i 表示：

  • 当前连续子数组的起点

然后：

1
total = 0

为什么每次外层循环都重新设成 0？

因为：

  • 只要起点变了
  • 我们就是在重新计算“从这个新起点出发”的所有区间和

接着看内层循环：

1
for j in range(i, len(nums)):

这里的 j 表示：

  • 当前连续子数组的终点

于是每次循环时，区间就是：

1
nums[i:j+1]

再看：

1
total += nums[j]

这句很巧妙。

它表示：

  • 不用每次都重新把区间和从头算一遍
  • 而是在前一个区间和的基础上，直接多加一个新元素

例如：

  • 先有 [4]
  • 再变成 [4,-1]
  • 再变成 [4,-1,2]

每次只是多加一个尾巴。

最后：

1
ans = max(ans, total)

表示如果当前区间和更大，就更新全局最大值。

4.5 用示例手动走一遍

还是：

1
[-2,1,-3,4,-1,2,1,-5,4]

从 i = 0 开始

依次得到：

  • [-2]，和是 -2
  • [-2,1]，和是 -1
  • [-2,1,-3]，和是 -4
  • …

这轮不会得到最终答案。

从 i = 3 开始

会依次得到：

  • [4]，和是 4
  • [4,-1]，和是 3
  • [4,-1,2]，和是 5
  • [4,-1,2,1]，和是 6

这时全局答案被更新成 6。

4.6 这个方法的问题在哪

它当然是正确的，但有一个很明显的问题：

  • 还是在枚举很多区间

也就是说，它虽然帮助我们理解了题目，但还不是最优思路。

5. 真正的关键转折：换一个问题来问

这题最重要的一步，不是背某个公式，而是换一个问法。

不要直接问：

  • 整个数组里的最大连续子数组和是多少？

而要问：

  • 如果我只看“以当前位置结尾”的子数组，最大和是多少？

这个问法非常关键。

因为一旦你只关心“以 i 结尾”，问题就会和前一个位置强相关。

6. 方法二：动态规划 / Kadane 算法

6.1 为什么这题可以做成动态规划

假设我们已经走到位置 i，当前元素是 nums[i]。

这时如果要考虑：

  • 以 i 结尾的最大连续子数组和

其实只会有两种可能：

  1. 直接从 nums[i] 自己重新开始
  2. 把前一个位置的最优连续和接过来，再加上 nums[i]

为什么只有这两种？

因为既然要求“以 i 结尾”，那这个子数组的最后一个元素一定是 nums[i]。

那么它前面那一部分，要么：

  • 根本不要了，从 i 自己开新段

要么：

  • 就是某个“以 i-1 结尾”的连续子数组

而为了让结果最大，那前一部分当然应该取“以 i-1 结尾的最优值”。

这就是动态规划的状态转移来源。

6.2 状态转移公式

于是有：

1
cur = max(nums[i], cur + nums[i])

这句人话意思就是：

  • 我是自己单独开一段更赚
  • 还是接在前面的连续段后面更赚

其中：

  • cur 表示“前一个位置结尾时的最优连续和”

7. Python Tutor 版代码

1
2
3
4
5
6
7
8
9
10
11
def max_sub_array(nums):
    cur = nums[0]
    ans = nums[0]

    for i in range(1, len(nums)):
        cur = max(nums[i], cur + nums[i])
        ans = max(ans, cur)

    return ans

print(max_sub_array([-2,1,-3,4,-1,2,1,-5,4]))

8. LeetCode 可提交版代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxSubArray(self, nums):
        cur = nums[0]
        ans = nums[0]

        for i in range(1, len(nums)):
            cur = max(nums[i], cur + nums[i])
            ans = max(ans, cur)

        return ans

9. 每一行代码在做什么

先看初始化：

1
2
cur = nums[0]
ans = nums[0]

这里两个变量的含义一定要分清：

  • cur：以当前位置结尾时，能拿到的最大连续和
  • ans：整个遍历过程中出现过的最大连续和

这两个变量看起来都像“最大值”，但其实层次完全不同。

9.1 cur 是局部状态

cur 只关心一件事：

  • 当前这个位置结尾，最好的连续和是多少

它不是全局答案。

9.2 ans 是全局答案

ans 才表示：

  • 到目前为止，所有位置里最大的连续和

再看循环：

1
for i in range(1, len(nums)):

因为第 0 位已经拿来初始化了，所以从第 1 位开始处理。

最核心的是这句：

1
cur = max(nums[i], cur + nums[i])

它必须彻底理解。

这里比较的是两种选择：

选择一：从自己重新开始

1
nums[i]

表示：

  • 前面的连续和太拖后腿了
  • 不如我自己重新开一段

选择二：把前面的最优状态接上

1
cur + nums[i]

表示：

  • 前面的连续和还有价值
  • 接上当前元素以后更赚

然后取这两个里的更大者。

再看：

1
ans = max(ans, cur)

这句表示：

  • 当前这个位置结尾的最优值已经算出来了
  • 现在拿它去和全局答案比较
  • 看看要不要更新全局最大值

这两句的顺序不能反。

为什么？

因为你必须先把当前位置的 cur 算对，才能拿它去更新 ans。

10. 用经典示例一步一步模拟

还是这组最经典的数据：

1
[-2,1,-3,4,-1,2,1,-5,4]

开始时：

  • cur = -2
  • ans = -2

走到 1

比较：

  • nums[i] = 1
  • cur + nums[i] = -2 + 1 = -1

显然 1 更大。

所以：

  • cur = 1
  • ans = 1

这一步的含义是：

  • 前面的 -2 太拖后腿了
  • 不如从 1 重新开始

走到 -3

比较：

  • 单独从 -3 开始，得到 -3
  • 把前面的 1 接上，得到 -2

这里 -2 更大，所以：

  • cur = -2
  • ans 仍然是 1

走到 4

比较：

  • 单独从 4 开始，得到 4
  • 把前面的 -2 接上，得到 2

显然 4 更大，所以：

  • cur = 4
  • ans = 4

这说明：

  • 到这里时，最优选择是从 4 开新段

再走到 -1

比较：

  • 单独从 -1 开始，得到 -1
  • 把前面的 4 接上，得到 3

于是：

  • cur = 3
  • ans 还是 4

再走到 2

比较：

  • 单独从 2 开始，得到 2
  • 接在前面，得到 5

于是：

  • cur = 5
  • ans = 5

再走到 1

比较：

  • 单独开始是 1
  • 接上前面是 6

于是：

  • cur = 6
  • ans = 6

这时候就已经达到了最终答案。

后面即使继续遍历，也不会超过 6。

11. 为什么这个转移这么重要

这题最值得你记住的，不是 Kadane 这个名字，而是它背后的动态规划思路：

  • 我们不是一下子求整个大问题
  • 而是先定义一个更容易递推的小状态

这个小状态就是：

  • 以当前位置结尾的最大连续和

一旦这个状态定义对了，后面整个解法就会变得非常短。

这也是很多动态规划题的共同特点：

  • 代码不一定长
  • 但状态定义特别关键

12. 这题顺手学到的 Python 语法

12.1 max(a, b)

用来比较两个选择里更大的那个。

12.2 从下标 1 开始遍历

1
for i in range(1, len(nums)):

因为第 0 位已经用于初始化。

12.3 变量滚动更新

这题没有真的开一个 dp 数组，而是只用一个 cur 保存前一状态。这是一种很常见的动态规划空间优化。

13. 这题最容易犯的错

13.1 把“连续子数组”理解成随便挑几个数

这题只能选连续的一段。

13.2 把 ans 初始化成 0

这样在全负数组里会出错。

13.3 没看懂 cur 的真正含义

cur 不是全局最大值，而是：

  • 以当前位置结尾的局部最优值

13.4 觉得这题是“贪心瞎蒙”

其实不是。

它本质上是动态规划，只是状态压缩得非常短。

14. 一句话复盘

这题的本质是：每走到一个新数字，都问自己一句——我要从这里重新开始，还是把前面的连续和接过来更赚？

15. 下一步怎么学

下一题 56. 合并区间 会回到数组专题，但重点会切到“排序后再处理结构关系”。