LeetCode 53 最大子数组和：原来动态规划可以这么简单
最近刷到 LeetCode 53《最大子数组和》，一开始看到“动态规划”几个字还有点发怵，总觉得要背公式、画状态表。
结果真正理解之后发现，这道题其实非常符合人的直觉。
核心思想只有一句话：
当前数字要不要和前面那段连续子数组接在一起？
理解了这句话，代码几乎就自己出来了。
题目描述
给定一个整数数组nums，找出一个具有最大和的连续子数组，并返回其最大和。
示例：
nums=[-2,1,-3,4,-1,2,1,-5,4]输出：
6因为连续子数组：
[4,-1,2,1]的和最大：
4+(-1)+2+1=6先别想动态规划
先站在一个普通人的角度思考。
假设你已经走到了某个数字面前。
比如来到数字：
4这时候你有两个选择：
方案一：接上前面的连续子数组
例如前面已经累计出了：
3那么现在可以变成：
3+4=7方案二：不要前面的了
直接从当前数字重新开始：
4那应该怎么选？
答案非常简单：
哪个大就选哪个。
如果前面的累计和是正数，就带上。
如果前面的累计和已经是负数，就直接扔掉。
因为负数只会拖后腿。
用示例一步一步走
题目：
[-2,1,-3,4,-1,2,1,-5,4]我们准备两个变量：
当前和 历史最大和第1个数字：-2
当前和：
-2历史最大：
-2第2个数字：1
现在问自己：
带上前面的好，还是重新开始？
-2+1=-11显然：
1>-1所以直接不要前面的。
当前和：
1历史最大：
1第3个数字：-3
继续思考：
1+(-3)=-2-3选大的：
-2当前和：
-2历史最大：
1第4个数字：4
继续判断：
-2+4=24显然：
4>2直接重新开始。
当前和：
4历史最大：
4第5个数字：-1
判断：
4+(-1)=3-1选：
3当前和：
3历史最大：
4第6个数字：2
判断：
3+2=52选：
5历史最大更新：
5第7个数字：1
判断：
5+1=61选：
6历史最大更新：
6第8个数字：-5
判断：
6+(-5)=1-5选：
1历史最大仍然：
6第9个数字：4
判断：
1+4=54选：
5历史最大依旧：
6最终答案：
6对应连续子数组：
[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_sumpre 表示什么？
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 算法，也是很多动态规划题目的入门模板。
如果一句话概括：
每走到一个数字面前，都问自己：带上前面更赚，还是从这里重新开始更赚。