LeetCode 剑指 Offer 42. 连续子数组的最大和
题目描述
题意分析
从非空整数数组中选择一段连续且非空的子数组，使其中元素之和最大，返回这个最大和。可以从任意位置开始、在任意位置结束，但不能跳过中间元素，也不能重排数组。
数组可能含负数，也可能全部为负。负数并不一定都要排除，因为它可能连接前后收益更大的部分；全负时仍必须选择至少一个元素，答案是其中最大的那个值，不能返回空子数组的和零。
解法：Kadane 动态规划
核心思路
[!blue]
按子数组的右端点分类。定义
cur为必须以当前位置结尾的非空子数组最大和，ans为已经处理过的所有右端点中的最大值。强调“必须以当前位置结尾”，才能保证下一个元素接上来时仍然连续。处理
nums[i]时，以它结尾的子数组只有两类：长度为一，只取nums[i]；长度至少为二，就必须接在某个以i - 1结尾的子数组之后。所有后一类都加上相同的当前值，因此只需保留其中最大的旧cur，转移为cur = max(nums[i], cur + nums[i])。两种选择的差别只在旧
cur。旧值为负时，它会拖累当前数，应从当前数重新开始；旧值非负时，接上它不会更差。Go 的符号判断正是这个转移的等价写法，判断的是前一段的总和，而不是看到当前元素为负就立刻断开。每得到新的
cur，再用它更新ans。局部结尾最优值可以下降，也可以换一个起点，但全局答案要保留以前已经出现过的最佳区间。任何非空子数组都有一个右端点，所以遍历全部结尾即可覆盖全部候选。用首元素同时初始化
cur、ans，再从第二个元素开始。这让初始状态就是一个真实非空子数组，单元素和全负输入都可以直接按同一规则处理；最终返回历史最优ans。
解题步骤
- 令
cur = ans = nums[0]，已经处理好只含首元素的情况。- 从下标
1开始遍历，比较单独取当前数与接在旧cur后面两种方案。- 保存两者较大值为新
cur，再执行ans = max(ans, cur)。- 所有结尾处理完后返回
ans。
代码实现
class Solution {
public int maxSubArray(int[] nums) {
// 从真实元素开始，保证全负数组也只能选择非空子数组。
int cur = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
// 当前数单独开始，或接在此前的连续后缀之后。
cur = Math.max(nums[i], cur + nums[i]);
ans = Math.max(ans, cur);
}
return ans;
}
}
func maxSubArray(nums []int) int {
// 从真实元素开始，保证全负数组也只能选择非空子数组。
cur := nums[0]
ans := nums[0]
for i := 1; i < len(nums); i++ {
// 旧后缀为负时会拖累当前数，因此从当前数重新开始。
if cur < 0 {
cur = nums[i]
} else {
cur += nums[i]
}
if cur > ans {
ans = cur
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素只进行一次常数时间的状态转移。
- 空间复杂度：$O(1)$，下一步只依赖前一位置的
cur，无需保存整张动态规划表。
关键点总结
[!green]
- 以当前位置结尾的最优和保证了后续拼接的连续性。
- 每步只有重新开始或接上旧后缀两类选择，旧后缀为负时应舍弃。
cur负责当前结尾，ans保留所有结尾的最好结果，并以真实首元素初始化。
易错点总结
[!yellow]
- 用零初始化答案或允许把局部结果归零，会让全负数组错误地选择空区间。
- 直接把当前数接到历史
ans后面，无法保证那段历史最优区间紧邻当前位置。- 只累加正数，或遇到负数就截断，会破坏连续性或丢掉需要跨过少量负数的最优区间。
- 最后返回
cur，会漏掉较早结束的最佳区间。- 首元素已经用于初始化，循环必须从下标
1开始，避免重复计入它。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 918. 环形子数组的最大和 | 中等 | 在最大连续和基础上增加首尾相接的情况，还要考虑总和减最小连续段。 |
| 152. 乘积最大子数组 | 中等 | 同样维护以当前位置结尾的最优状态，但负数乘法会交换大小，需同时记录最大与最小乘积。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！