LeetCode 53. 最大子数组和
题目描述
题意分析
在数组中选出一段非空、连续的元素，使它们的和最大，返回这个最大和，不需要返回子数组本身。
连续表示不能跳过中间元素，非空表示至少选一个数。因此，即使数组中的数全为负数，也必须选出其中最大的那个，不能用空数组的和
0作为答案。
解法：动态规划滚动变量
核心思路
[!blue]
从左到右遍历，用
current表示“必须以当前位置结尾的最大子数组和”。因为要求连续，加入当前元素时只有两种选择：接在前一个位置结尾的子数组后面，或者舍弃前面的一段，从当前元素重新开始。接在前面时，为什么只需保留上一位置的最大和？所有候选子数组都会加上同一个当前元素，加之前较小的和，加之后仍然较小。因此只保留其中最大的一个就足够，不需要记住每一种起点。
前一段的和为正时，接上它能让结果更大；为负时，接上它反而会拖低结果，应重新开始；为零时两种选择的和相同。因此每轮更新为
current = max(nums[i], current + nums[i])，右侧的current是更新前、以上一个位置结尾的最大子数组和。
current只回答“以这里结尾，最大和是多少”，整道题的最优子数组可能在更早的位置结束，所以还要用ans保存遍历过程中最大的current。两个变量都用首元素初始化，既保证子数组非空，也能正确处理全负数组。
解题步骤
- 用
nums[0]初始化current和ans。- 从第二个元素开始，比较“单独选择当前元素”和“接在上一段后面”的和，取较大值更新
current。- 用
ans = max(ans, current)保存到目前为止的最大和。- 遍历结束后返回
ans。
代码实现
class Solution {
public int maxSubArray(int[] nums) {
// 非空子数组必须选一个数，不能用零压过全负输入。
int current = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
// current 是以当前位置结尾的最优和，接续或重新开始后再更新全局答案。
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:] {
// current 是以当前位置结尾的最优和，旧片段有正贡献才接续，再更新全局答案。
if current > 0 {
current += num
} else {
current = num
}
if current > ans {
ans = current
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，只遍历一次数组。
- 空间复杂度：$O(1)$，只维护当前结尾的最大和与全局最大和。
关键点总结
[!green]
- 状态含义是“必须以当前位置结尾”，不是前缀中的最大值。
- 前一段和为负时应从当前元素重新开始。
- 滚动变量即可，无需保存完整 DP 数组。
易错点总结
[!yellow]
- 将初值设为
0，会让全负数组错误返回0。- 只返回最后的
current，忽略了更早出现的最优区间。- 题目要求连续子数组，不能跳过中间元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 918. 环形子数组的最大和 | 中等 | 在最大连续和基础上增加首尾相接的情况，还要考虑总和减最小连续段。 |
| 152. 乘积最大子数组 | 中等 | 同样维护以当前位置结尾的最优状态，但负数乘法会交换大小，需同时记录最大与最小乘积。 |
| 1186. 删除一次得到子数组最大和 | 中等 | 维护以当前位置结尾的最优连续区间；本题记录最大连续和，该题增加已经删除一次的状态。 |
| 1567. 乘积为正数的最长子数组长度 | 中等 | 维护以当前位置结尾的最优连续区间；本题记录最大连续和，该题只维护正负乘积对应的最长长度。 |
| 补充题 155. 最大子数组和及其起点 | 中等 | 都用当前结尾的最优子数组和递推；补充题还需在重新起段时更新起点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！