力扣hot100-53.最大子数组和-动态规划详解

LeetCode 53. 最大子数组和：动态规划详解

1. 这道题到底在问什么

LeetCode 53「最大子数组和」要求：

在整数数组 nums 中，找一个连续且非空的子数组，使它的元素和最大，返回这个最大和。

关键词是：

1. 子数组：必须连续。
2. 最大和：不是找最大的单个元素，而是找和最大的连续区间。
3. 非空：至少必须选择一个元素。

例如：

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

最大和来自：

[4, -1, 2, 1]

它的和是：

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

所以答案是：

6

2. 先从暴力法理解问题

最直接的想法是枚举每一个连续子数组，再计算其和。

例如对于：

nums = [1, -2, 3]

需要考虑：

[1]
[1, -2]
[1, -2, 3]
[-2]
[-2, 3]
[3]

这种做法能正确解决问题，但会产生大量重复计算。

当我们已经算过 [1, -2] 的和后，再算 [1, -2, 3] 时，虽然可以继续加 3，但仍然需要对每个起点重复枚举右边界。

时间复杂度通常是：

O(n^2)

这题可以利用动态规划，在一次遍历中完成。

3. 动态规划状态到底表示什么

定义：

dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和。

这里最关键的是：

必须以 nums[i] 结尾。

dp[i] 不是下面这种含义：

nums[0..i] 范围内的最大子数组和。

例如：

nums = [-2, 1, -3]

当 i = 2 时：

nums[0..2] 范围内的最大子数组和是 1，对应 [1]。

但：

dp[2] 是必须以 nums[2] = -3 结尾的最大和。

因此：

dp[2] = -2，对应 [1, -3]。

状态必须明确“以 i 结尾”，是因为这样才能自然地从 dp[i – 1] 推导到 dp[i]。

4. 到当前位置时，只有两种选择

现在考虑 nums[i]。

我们要计算的是：

以 nums[i] 结尾的连续子数组最大和。

由于子数组必须连续，并且必须以 nums[i] 结尾，所以只有两种可能：

1. 不要前面的元素，从 nums[i] 自己重新开始。
2. 把 nums[i] 接在“以 nums[i – 1] 结尾的最佳子数组”后面。

第一种情况的和是：

nums[i]

第二种情况的和是：

dp[i – 1] + nums[i]

因此递推公式是：

dp[i] = max(dp[i – 1] + nums[i], nums[i])

这不是从很多选择里随便挑两个，而是由“连续且必须以 i 结尾”强制得到的全部可能。

5. 为什么前面和为负数时要放弃

假设：

dp[i – 1] = -2
nums[i] = 4

两种选择分别是：

接在前面：-2 + 4 = 2
从当前重新开始：4

显然选择 4 更好。

原因是：

如果前面累计出来的最佳和已经是负数，继续带着它只会拖累当前元素。

但不要把这句话误记成：

遇到负数就清零。

这是错误的。

例如：

dp[i – 1] = 5
nums[i] = -1

此时：

接在前面：5 + (-1) = 4
重新开始：-1

即使当前元素是负数，前面的正收益仍然有价值，应该保留。

真正的判断是：

比较 dp[i – 1] + nums[i] 和 nums[i]，选择更大的一个。

6. 全局答案为什么还需要 res

dp[i] 只表示：

以 nums[i] 结尾的最大和。

最终答案却是：

所有 dp[i] 中的最大值。

因此需要一个变量 res：

res = max(res, dp[i])

例如：

nums = [-2, 1, -3]
dp = [-2, 1, -2]

最后一个状态：

dp[2] = -2

但真正答案是：

1

它出现在 dp[1]。

所以不能直接返回最后一个 dp[n – 1]，必须维护所有状态中的最大值。

7. 初始化为什么不能都写成 0

初始状态应当是：

dp[0] = nums[0];
int res = nums[0];

不能初始化为 0。

因为题目要求子数组至少包含一个元素。

例如：

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

正确答案是：

-2

如果把 dp 和 res 都初始化为 0，最后会得到 0。

但 0 的含义是“不选任何元素”，这不满足“子数组非空”的要求。

因此必须让第一个元素作为真实的初始子数组：

dp[0] = nums[0]
res = nums[0]

这样即使全是负数，也能正确返回其中最大的元素。

8. 用示例完整推导 dp 数组

示例：

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

初始化：

dp[0] = -2
res = -2

之后从前往后推导：

最终：

dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
res = 6

res = 6 对应的连续子数组是：

[4, -1, 2, 1]

9. Java 代码完整注释

class Solution {
public int maxSubArray(int[] nums) {
// 题目保证 nums 非空。
// 这里保留空数组判断，便于独立调用时避免访问 nums[0]。
if (nums.length == 0) {
return 0;
}

// dp[i] 表示：以 nums[i] 结尾的连续子数组最大和。
int[] dp = new int[nums.length];

// 初始化：只有 nums[0] 一个元素时，最大和只能是 nums[0]。
dp[0] = nums[0];

// res 表示目前所有 dp[i] 中的最大值，也就是全局最大子数组和。
// 不能初始化为 0，否则全负数组会得到错误答案。
int res = nums[0];

// 从前往后计算 dp 数组。
for (int i = 1; i < nums.length; i++) {
// 以 nums[i] 结尾时有两种选择：
// 1. 接在以前一个位置结尾的最佳子数组后面。
// 2. 放弃前面部分，从 nums[i] 自己重新开始。
dp[i] = Math.max(dp[i – 1] + nums[i], nums[i]);

// 当前 dp[i] 可能刷新全局最大和。
res = Math.max(res, dp[i]);
}

return res;
}
}

10. 状态压缩只是后续优化

观察递推公式：

dp[i] = max(dp[i – 1] + nums[i], nums[i])

计算 dp[i] 时只使用 dp[i – 1]，不需要更早的状态。

因此，完整理解后，可以用一个变量代替整个 dp 数组，把空间从 O(n) 优化到 O(1)。

但是这只是空间优化，不是这道题的核心思路。

对于刚学习动态规划时，先写出完整 dp 数组更清晰：

状态是什么。
状态如何转移。
状态怎样初始化。
最终答案从哪里取。

都能直接在代码中看到。

11. 复杂度分析

时间复杂度：

O(n)

数组只遍历一次。

空间复杂度：

O(n)

因为使用了长度为 n 的 dp 数组。

如果之后进行状态压缩，空间复杂度可以优化到 O(1)，但本题的主代码保留 dp 数组以突出动态规划状态。

12. 总结

这道题的动态规划状态是：

dp[i]：以 nums[i] 结尾的连续子数组最大和。

递推公式是：

dp[i] = max(dp[i – 1] + nums[i], nums[i])

含义是：

要么让当前元素接上前面的连续子数组，
要么丢掉前面的部分，从当前元素重新开始。

最终答案不是最后一个状态，而是：

res = max(dp[0], dp[1], …, dp[n – 1])

最容易错的地方是初始化：

dp[0] 和 res 必须初始化为 nums[0]，不能初始化为 0。

因为题目要求子数组至少包含一个元素，必须正确处理全负数组。