LeetCode 53 最大子数组和：原来动态规划可以这么简单

2026/6/19 7:53:20

LeetCode 53 最大子数组和：原来动态规划可以这么简单

最近刷到 LeetCode 53《最大子数组和》，一开始看到“动态规划”几个字还有点发怵，总觉得要背公式、画状态表。

结果真正理解之后发现，这道题其实非常符合人的直觉。

核心思想只有一句话：

当前数字要不要和前面那段连续子数组接在一起？

理解了这句话，代码几乎就自己出来了。

题目描述

给定一个整数数组nums，找出一个具有最大和的连续子数组，并返回其最大和。

示例：

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

输出：

因为连续子数组：

[4,-1,2,1]

的和最大：

4+(-1)+2+1=6

先别想动态规划

先站在一个普通人的角度思考。

假设你已经走到了某个数字面前。

比如来到数字：

这时候你有两个选择：

方案一：接上前面的连续子数组

例如前面已经累计出了：

那么现在可以变成：

3+4=7

方案二：不要前面的了

直接从当前数字重新开始：

那应该怎么选？

答案非常简单：

哪个大就选哪个。

如果前面的累计和是正数，就带上。

如果前面的累计和已经是负数，就直接扔掉。

因为负数只会拖后腿。

用示例一步一步走

题目：

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

我们准备两个变量：

当前和 历史最大和

第1个数字：-2

当前和：

-2

历史最大：

-2

第2个数字：1

现在问自己：

带上前面的好，还是重新开始？

-2+1=-1

显然：

1>-1

所以直接不要前面的。

当前和：

历史最大：

第3个数字：-3

继续思考：

1+(-3)=-2

-3

选大的：

-2

当前和：

-2

历史最大：

第4个数字：4

继续判断：

-2+4=2

显然：

4>2

直接重新开始。

当前和：

历史最大：

第5个数字：-1

判断：

4+(-1)=3

-1

选：

当前和：

历史最大：

第6个数字：2

判断：

3+2=5

选：

历史最大更新：

第7个数字：1

判断：

5+1=6

选：

历史最大更新：

第8个数字：-5

判断：

6+(-5)=1

-5

选：

历史最大仍然：

第9个数字：4

判断：

1+4=5

选：

历史最大依旧：

最终答案：

对应连续子数组：

[4,-1,2,1]

代码为什么这样写？

完整代码：

fromtypingimportListclassSolution:defmaxSubArray(self,nums:List[int])->int:pre=0max_sum=float('-inf')fornuminnums:pre=max(pre+num,num)max_sum=max(max_sum,pre)returnmax_sum

pre 表示什么？

pre

表示：

以当前数字结尾时，最大的连续子数组和。

比如来到数字4：

pre=6

说明：

某个连续子数组...4

结尾是当前数字，并且和最大。

为什么是

pre=max(pre+num,num)

因为只有两种选择：

接上前面

pre+num

从当前数字重新开始

num

选大的那个：

pre=max(pre+num,num)

这就是整道题的核心。

max_sum 干什么？

max_sum

负责记录历史最好成绩。

因为：

pre

只代表当前数字结尾的情况。

而答案可能出现在任何位置。

所以需要一个变量全程记录：

max_sum=max(max_sum,pre)

全负数为什么也能正确处理？

例如：

[-3,-1,-2]

过程：

当前=-3最大=-3当前=-1最大=-1当前=-2最大=-1

最终返回：

-1

正确答案正是：

[-1]

这道题为什么属于动态规划？

动态规划的本质其实就一句话：

当前结果依赖前一步结果。

这里：

当前的pre

依赖：

上一轮的pre

因为：

pre=max(pre+num,num)

里面直接用了上一轮计算出来的结果。

所以它符合动态规划的思想。

为什么很多人说它还有贪心思想？

因为每一步都在做局部最优选择：

带前面的 还是重新开始

直接选更大的那个。

这种“当前先选最优”的思路，又带有明显的贪心特点。

所以很多面试官会说：

Kadane 算法本质是动态规划，但理解起来更像贪心。

Kadane 算法到底记什么？

其实不用死记公式。

记住下面这句话就够了：

前面的连续和如果是正数，就带上；如果已经变成负数，就直接扔掉，从当前数字重新开始。

代码里对应的就是：

pre=max(pre+num,num)

总结

这道题最容易让人误以为很复杂，但实际上思路非常朴素。

整个过程只做两件事：

判断当前数字是接在前面后面，还是重新开始；
顺便记录全程出现过的最大和。

最终只需要遍历一次数组。

时间复杂度：

O(n)

空间复杂度：

O(1)

这就是经典的 Kadane 算法，也是很多动态规划题目的入门模板。

如果一句话概括：

每走到一个数字面前，都问自己：带上前面更赚，还是从这里重新开始更赚。

LeetCode 53 最大子数组和：原来动态规划可以这么简单