难度：Medium | 标签：数组、动态规划、贪心、分治 | DP 入门必刷 ⭐
给你一个整数数组 nums，请找出一个具有 最大和 的 连续子数组（子数组最少包含一个元素），返回其最大和。
约束
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
示例
| 输入 | 输出 | 子数组 |
|---|---|---|
[-2,1,-3,4,-1,2,1,-5,4] |
6 |
[4,-1,2,1] |
[1] |
1 |
[1] |
[5,4,-1,7,8] |
23 |
全数组 |
题目链接：https://leetcode.cn/problems/maximum-subarray/
从暴力到 DP 的思路：
- 暴力枚举所有子数组 O(n³)，加上前缀和优化到 O(n²)，但仍未抹去重复计算。
- 关键观察：枚举以
i结尾的最大子数组时，“以 i-1 结尾的最大子数组”不是负的话就该接上，负的话从 i 重起。于是状态只依赖前一个，这就是 DP。
定义 f(i) = 以 nums[i] 结尾 的最大子数组和。
转移：
含义：要么 接着前面的扩展，要么 从 i 重新开始（前面的负贡献就丢掉）。
最终答案：max(f(0), f(1), ..., f(n-1))。
学习点 ①：DP 状态定义要"以 i 结尾"而非"前 i 个的最大"，才能保证连续性。这是一类 DP 题共同的套路（同样适用于 LIS、乘积最大子数组等）。
f(i) 只依赖 f(i-1)，用一个变量滚动即可。
维护当前累加和 cur：若 cur < 0，对未来一定是负贡献，清零重启。
| 坑 | 处理 |
|---|---|
全负数组（如 [-3,-1,-2]）误返回 0 |
答案初始化为 Integer.MIN_VALUE 或 nums[0]，不能 是 0 |
| 用滑动窗口正负判断 | 元素含负数时窗口不单调，滑动窗口失效，必须 DP |
class Solution {
public int maxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(cur + nums[i], nums[i]); // 接 or 重启
best = Math.max(best, cur);
}
return best;
}
}记忆口诀：
"接着走，还是重开？取大者；全程最大记 best。"
把数组对半分，最大子数组要么在左、要么在右、要么 横跨中点。横跨情况从中点向两边各做一次贪心扩展。
class Solution {
public int maxSubArray(int[] nums) {
return divide(nums, 0, nums.length - 1);
}
private int divide(int[] a, int l, int r) {
if (l == r) return a[l];
int m = (l + r) >>> 1;
int leftMax = divide(a, l, m);
int rightMax = divide(a, m + 1, r);
// 横跨中点：从 m 向左、从 m+1 向右各取最大前缀
int sum = 0, lMax = Integer.MIN_VALUE;
for (int i = m; i >= l; i--) { sum += a[i]; lMax = Math.max(lMax, sum); }
sum = 0; int rMax = Integer.MIN_VALUE;
for (int i = m + 1; i <= r; i++) { sum += a[i]; rMax = Math.max(rMax, sum); }
return Math.max(Math.max(leftMax, rightMax), lMax + rMax);
}
}分治版是 「线段树」 解决区间最大子段和的雏形（支持单点修改 + 区间查询）。
| 解法 | 时间 | 空间 |
|---|---|---|
| Kadane | O(n) | O(1) |
| 分治 | O(n log n) | O(log n) 递归栈 |
nums = [-2,1,-3,4,-1,2,1,-5,4]
| i | nums[i] | cur (接 vs 重开) | best |
|---|---|---|---|
| 0 | -2 | -2 | -2 |
| 1 | 1 | max(-2+1, 1)=1 | 1 |
| 2 | -3 | max(1-3, -3)=-2 | 1 |
| 3 | 4 | max(-2+4, 4)=4 | 4 |
| 4 | -1 | max(4-1, -1)=3 | 4 |
| 5 | 2 | max(3+2, 2)=5 | 5 |
| 6 | 1 | max(5+1, 1)=6 | 6 |
| 7 | -5 | max(6-5, -5)=1 | 6 |
| 8 | 4 | max(1+4, 4)=5 | 6 |
输出 6 ✅
以 i 结尾的最大子数组：要么把 i 接上前面，要么从 i 重新开始。
Q1：为什么状态是"以 i 结尾"，而不是"前 i 个的最大子数组和"？
A：“以 i 结尾”才能表达连续性：f(i-1) 的子数组以 i-1 结尾，接上 nums[i] 则仍为连续。若定义为“前 i 个的最大子数组和”，那个子数组可能末尾不是 i-1，加上 nums[i] 就不连续了。
Q2：全负数组返回 0 对不对？
A：不对。题目要求子数组至少一个元素，如 [-3,-1,-2] 应返 -1。初始化 best = nums[0]（不能是 0），算法天然正确。
Q3：为什么不能用滑动窗口（双指针）？ A：滑动窗口需要“扩展一定使之变大、收缩一定变小”的单调性。含负数时扩展可能让和变小，收缩可能让和变大，没有单调性，滑窗失效。这是题目“含负数”与“全正数”的本质区别。
Q4：为什么叫 Kadane？ A：Jay Kadane 上世纪 80 年代提出该算法，是“DP 滑动状态”的原型。面试可以报出名字加分，但不要独压这条。
Q5：怎么同时返回最大子数组的起止下标？
A：重启时（cur = nums[i]）记 tmpStart = i；更新 best 时记 [tmpStart, i]。
Q6：分治版里左半为什么写 divide(l, mid) 而不是 divide(l, mid - 1)？
A：区间是闭区间 [l, r]，划分必须不重不漏地覆盖整个区间。
- 左半
[l, mid]+ 右半[mid+1, r]=[l, r]✅ - 若写成
[l, mid-1]+[mid+1, r]，nums[mid]就被两边都丢掉，结果错；而且当l == r-1时mid = l，devide(l, mid-1)变成devide(l, l-1)，base casel == r也命中不了，要么死循环要么爆栈。
这和二分查找里
r = mid - 1不一样：二分时已经"测过nums[mid]不是目标"，所以排除；分治里mid还要参与左半递归和跨中点求和，不能排除。跨中点求和
lmax + rmax - nums[mid]也是建立在"mid同属左半"的前提上——左右两段都把nums[mid]算进去了，所以减一次。
- "改成求最小子数组和呢？" → 同样模板，交换 max/min 即可；或求总和 − 最大子数组和。
- "求乘积最大子数组呢？" → 负数 × 负数 = 正，要 同时维护 max 与 min，遇到负数交换。即 LC 152。
- "环形数组的最大子数组和呢？" → 两种情况取最大：a) 不跨环→ Kadane；b) 跨环→
total - 最小子数组和。注意全负数要特判。即 LC 918。 - "允许删除一个元素后的最大子数组和？" → 双状态 DP：
f[i][0]不删、f[i][1]已删。即 LC 1186。 - "返回所有子数组中第 k 大的和呢？" → 前缀和 + 堆；或排序后二分。实际面试少见但可能被追问。
- "数据流场景（来一个处理一个）？" → Kadane 天然在线：
cur = max(cur+x, x); best = max(best, cur);。
- 为什么状态要"以 i 结尾"？→ 这样保证子数组连续；如果定义"前 i 个的最大"，无法表达"不取 i" vs "取 i" 的连续性。
- 全负数组怎么办？→ 初始化
best = nums[0]（不能是 0），算法天然正确。 - 数据流场景？→ Kadane 天然支持，每来一个
x，cur = max(cur+x, x); best = max(best, cur);。 - 如何返回最大子数组的 下标区间 ？→ 重启时记录
start = i，更新best时记录[start, i]。
- LC 152. 乘积最大子数组（同时维护 max/min）
- LC 918. 环形子数组的最大和（断环：
max子段和vstotal - min子段和） - LC 1186. 删除一次得到子数组最大和（双状态 DP）
- LC 363. 矩形区域不超过 K 的最大数值和（前缀和 + 有序集合）
- LC 209. 长度最小的子数组（同思路但目标改为和 ≥ s）