LeetCode 53 最大子数组和原来动态规划可以这么简单最近刷到 LeetCode 53《最大子数组和》一开始看到“动态规划”几个字还有点发怵总觉得要背公式、画状态表。结果真正理解之后发现这道题其实非常符合人的直觉。核心思想只有一句话当前数字要不要和前面那段连续子数组接在一起理解了这句话代码几乎就自己出来了。题目描述给定一个整数数组nums找出一个具有最大和的连续子数组并返回其最大和。示例nums[-2,1,-3,4,-1,2,1,-5,4]输出6因为连续子数组[4,-1,2,1]的和最大4(-1)216先别想动态规划先站在一个普通人的角度思考。假设你已经走到了某个数字面前。比如来到数字4这时候你有两个选择方案一接上前面的连续子数组例如前面已经累计出了3那么现在可以变成347方案二不要前面的了直接从当前数字重新开始4那应该怎么选答案非常简单哪个大就选哪个。如果前面的累计和是正数就带上。如果前面的累计和已经是负数就直接扔掉。因为负数只会拖后腿。用示例一步一步走题目[-2,1,-3,4,-1,2,1,-5,4]我们准备两个变量当前和 历史最大和第1个数字-2当前和-2历史最大-2第2个数字1现在问自己带上前面的好还是重新开始-21-11显然1-1所以直接不要前面的。当前和1历史最大1第3个数字-3继续思考1(-3)-2-3选大的-2当前和-2历史最大1第4个数字4继续判断-2424显然42直接重新开始。当前和4历史最大4第5个数字-1判断4(-1)3-1选3当前和3历史最大4第6个数字2判断3252选5历史最大更新5第7个数字1判断5161选6历史最大更新6第8个数字-5判断6(-5)1-5选1历史最大仍然6第9个数字4判断1454选5历史最大依旧6最终答案6对应连续子数组[4,-1,2,1]代码为什么这样写完整代码fromtypingimportListclassSolution:defmaxSubArray(self,nums:List[int])-int:pre0max_sumfloat(-inf)fornuminnums:premax(prenum,num)max_summax(max_sum,pre)returnmax_sumpre 表示什么pre表示以当前数字结尾时最大的连续子数组和。比如来到数字4pre6说明某个连续子数组...4结尾是当前数字并且和最大。为什么是premax(prenum,num)因为只有两种选择接上前面prenum从当前数字重新开始num选大的那个premax(prenum,num)这就是整道题的核心。max_sum 干什么max_sum负责记录历史最好成绩。因为pre只代表当前数字结尾的情况。而答案可能出现在任何位置。所以需要一个变量全程记录max_summax(max_sum,pre)全负数为什么也能正确处理例如[-3,-1,-2]过程当前-3最大-3当前-1最大-1当前-2最大-1最终返回-1正确答案正是[-1]这道题为什么属于动态规划动态规划的本质其实就一句话当前结果依赖前一步结果。这里当前的pre依赖上一轮的pre因为premax(prenum,num)里面直接用了上一轮计算出来的结果。所以它符合动态规划的思想。为什么很多人说它还有贪心思想因为每一步都在做局部最优选择带前面的 还是重新开始直接选更大的那个。这种“当前先选最优”的思路又带有明显的贪心特点。所以很多面试官会说Kadane 算法本质是动态规划但理解起来更像贪心。Kadane 算法到底记什么其实不用死记公式。记住下面这句话就够了前面的连续和如果是正数就带上如果已经变成负数就直接扔掉从当前数字重新开始。代码里对应的就是premax(prenum,num)总结这道题最容易让人误以为很复杂但实际上思路非常朴素。整个过程只做两件事判断当前数字是接在前面后面还是重新开始顺便记录全程出现过的最大和。最终只需要遍历一次数组。时间复杂度O(n)空间复杂度O(1)这就是经典的 Kadane 算法也是很多动态规划题目的入门模板。如果一句话概括每走到一个数字面前都问自己带上前面更赚还是从这里重新开始更赚。
