知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 10 - 最大子数组和 ## 题目(LeetCode 53) 找到具有最大和的连续子数组,返回其最大和。 ``` 输入:[-2, 1, -3, 4, -1, 2, 1, -5, 4] 输出:6(子数组 [4, -1, 2, 1]) ``` ## 先搞清楚:子数组 vs 子序列 ``` 子数组(Subarray):必须连续 [-2, 1, -3] 是子数组 [-2, -3, 1] 不是子数组(顺序变了) 子序列(Subsequence):不要求连续 [-2, -3, 1] 是子序列 本题求的是子数组(连续的) ``` ## 大白话理解 走到每个位置,做一个决定: > 把前面的累加和带上,还是从自己重新开始? ``` 如果前面的累加和是正数 → 带上它,能让总和更大 如果前面的累加和是负数 → 丢掉它,从自己重新开始(负数只会拖后腿) ``` 生活类比:你在路上捡钱,每个位置有正数(捡到钱)或负数(丢了钱)。你可以从任意位置开始,到任意位置结束,问最多能捡多少钱。 ## 四步法 ``` 第 1 步:dp[i] = 以 nums[i] 结尾的最大子数组和 注意:一定包含 nums[i],不是"前 i 个元素中的最大子数组和" 第 2 步:dp[i] = max(nums[i], dp[i-1] + nums[i]) = nums[i] + max(0, dp[i-1]) 如果 dp[i-1] > 0:带上前面的累加和 如果 dp[i-1] <= 0:从 nums[i] 重新开始 第 3 步:dp[0] = nums[0](只有一个元素,就是它自己) 第 4 步:从左到右,最终答案是 max(dp[0..n-1]) ``` ### 为什么 dp[i] 要"以 nums[i] 结尾"? ``` 如果 dp[i] 定义为"前 i 个元素中的最大子数组和", 那 dp[i] 和 dp[i-1] 的关系就不好推导了 (因为最大子数组可能在任意位置结束) "以 nums[i] 结尾"固定了子数组的右端点, 这样 dp[i] 和 dp[i-1] 的关系就清晰了: dp[i] = dp[i-1] + nums[i](把 nums[i] 接在前面的子数组后面) 或者 dp[i] = nums[i](从 nums[i] 重新开始) ``` ## 手动模拟(这是理解的关键) ``` nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] dp[0] = -2(只有 -2,没得选) globalMax = -2 i=1 (nums[1]=1): dp[0] = -2 < 0,丢掉前面的 dp[1] = max(1, -2+1) = max(1, -1) = 1 globalMax = max(-2, 1) = 1 当前最优子数组:[1] i=2 (nums[2]=-3): dp[1] = 1 > 0,带上前面的 dp[2] = max(-3, 1+(-3)) = max(-3, -2) = -2 globalMax = max(1, -2) = 1 当前最优子数组:[1](不更新) i=3 (nums[3]=4): dp[2] = -2 < 0,丢掉前面的 dp[3] = max(4, -2+4) = max(4, 2) = 4 globalMax = max(1, 4) = 4 当前最优子数组:[4] i=4 (nums[4]=-1): dp[3] = 4 > 0,带上前面的 dp[4] = max(-1, 4+(-1)) = max(-1, 3) = 3 globalMax = max(4, 3) = 4 当前最优子数组:[4](不更新) i=5 (nums[5]=2): dp[4] = 3 > 0,带上前面的 dp[5] = max(2, 3+2) = max(2, 5) = 5 globalMax = max(4, 5) = 5 当前最优子数组:[4, -1, 2] i=6 (nums[6]=1): dp[5] = 5 > 0,带上前面的 dp[6] = max(1, 5+1) = max(1, 6) = 6 globalMax = max(5, 6) = 6 当前最优子数组:[4, -1, 2, 1] ← 最终答案 i=7 (nums[7]=-5): dp[6] = 6 > 0,带上前面的 dp[7] = max(-5, 6+(-5)) = max(-5, 1) = 1 globalMax = max(6, 1) = 6(不更新) i=8 (nums[8]=4): dp[7] = 1 > 0,带上前面的 dp[8] = max(4, 1+4) = max(4, 5) = 5 globalMax = max(6, 5) = 6(不更新) dp 数组:[-2, 1, -2, 4, 3, 5, 6, 1, 5] 答案 = globalMax = 6 ✓(子数组 [4, -1, 2, 1]) ``` ## 代码 ```java public int maxSubArray(int[] nums) { int curMax = nums[0], globalMax = nums[0]; for (int i = 1; i < nums.length; i++) { curMax = Math.max(nums[i], curMax + nums[i]); globalMax = Math.max(globalMax, curMax); } return globalMax; } ``` 这就是 Kadane 算法,O(n) 时间,O(1) 空间。 ## 为什么不能用滑动窗口? ``` 滑动窗口的前提:窗口扩大时和增大,窗口缩小时和减小 → 这样才能通过移动左右指针找到最优窗口 但本题有负数! 窗口扩大时,加入负数会让和减小 → 滑动窗口的单调性被破坏,无法使用 DP 没有这个限制,每个位置独立决策:带上前面的还是重新开始 ``` ## 注意:容易困惑的地方 ``` Q:dp[i] 是"以 nums[i] 结尾的最大子数组和",那最终答案是 dp[n-1] 吗? A:不是!最大子数组不一定以最后一个元素结尾。 最终答案是 max(dp[0], dp[1], ..., dp[n-1]),即所有 dp 值的最大值。 Q:如果所有数都是负数怎么办? A:dp[i] = max(nums[i], dp[i-1]+nums[i]) 当所有数都是负数时,每次都会选 nums[i](重新开始) 最终答案是最大的那个负数,这是正确的(子数组至少要有一个元素) Q:能不能返回空子数组(和为 0)? A:题目要求非空子数组,所以不能返回 0。 如果题目允许空子数组,只需要在最后和 0 取最大值即可。 ``` ## 一句话总结 Kadane 算法:前面的和是正数就带上,是负数就丢掉重新开始。最终答案是所有 dp 值的最大值。 --- 上一篇:[09 - 不同路径](./09-unique-paths.md) | 下一篇:[11 - 单词拆分](./11-word-break.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入