LeetCode 53. 最大子数组和
目录
题目描述
题意分析
给定整数数组
nums，找出一个非空连续子数组使其元素和最大，返回这个和。三个词决定了全部设计。「连续」意味着答案是一段区间，于是每个位置只面临二选一：接在前面那段后面，或者从自己重新开一段。「非空」意味着必须选至少一个元素——数组可能全是负数（如
[-2,-1]，答案是-1），所以答案的初值绝不能是 0，否则会返回空子数组的和。「最大」则要求在所有右端点上取全局最优。暴力枚举所有区间是 $O(n^2)$。优化的入手点是找一个能递推的状态。直接定义「前
i个元素中的最大子数组和」是行不通的——知道了前i个的答案，无法推出前i+1个的答案，因为新元素能否接上取决于那段最优子数组是否恰好在位置i结束，而这个信息被丢掉了。正确的状态定义要加上「以当前位置结尾」这个约束：
cur= 必须以nums[i]结尾的最大连续和。约束反而让递推成立了，因为「以i+1结尾」的段一定包含nums[i+1]，它要么紧接在「以i结尾」的最优段后面，要么单独成段。这是本题最核心的一步，也是动态规划里「把状态定得更窄反而更好推」的经典范例。全局答案则在每个位置用
cur刷新一次——因为最大子数组可以在任意位置结束，遍历所有结束位置就覆盖了所有可能。
解法：动态规划滚动变量
核心思路
设
current为“必须以当前位置结尾”的最大子数组和。对当前数字只有两种选择：单独开始，或接在前一段后面，因此current = max(nums[i], current + nums[i])。
解题步骤
- 用首元素初始化
current和答案，保证全负数组也能正确处理。- 从第二个元素开始更新
current。- 每轮用
current更新全局最大值。- 遍历结束后返回全局最大值。
代码实现
class Solution {
public int maxSubArray(int[] nums) {
int current = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
ans = Math.max(ans, current);
}
return ans;
}
}
func maxSubArray(nums []int) int {
current, ans := nums[0], nums[0]
for _, num := range nums[1:] {
if current > 0 {
current += num
} else {
current = num
}
if current > ans {
ans = current
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。
关键点总结
- 状态含义是“必须以当前位置结尾”，不是前缀中的最大值。
- 前一段和为负时应从当前元素重新开始。
- 滚动变量即可，无需保存完整 DP 数组。
易错点总结
- 将初值设为
0，会让全负数组错误返回0。- 只返回最后的
current，忽略了更早出现的最优区间。- 题目要求连续子数组，不能跳过中间元素。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 121. 买卖股票的最佳时机 | 简单 | 与解法二同一模型：当前值减历史最小值 |
| 152. 乘积最大子数组 | 中等 | 改成乘积后负负得正，需同时维护以当前结尾的最大值与最小值 |
| 918. 环形子数组的最大和 | 中等 | 环形数组，用「总和减最小子数组和」处理跨界情形，注意全负特判 |
| 560. 和为 K 的子数组 | 中等 | 前缀和加哈希，展示解法二框架在「求个数」场景下的延伸 |
| 1186. 删除一次得到子数组最大和 | 中等 | Kadane 加一维状态，记录「是否已使用删除机会」 |
| 1191. K 次串联后最大子数组之和 | 中等 | 数组重复 K 次，需分类讨论总和正负并结合前后缀最大和 |
| 剑指 Offer 42. 连续子数组的最大和 | 简单 | 与本题同题，可直接套用 |
| 面试题 16.17. 连续数列 | 简单 | 与本题同题，可直接套用 |