LeetCode 面试题 16.17. 连续数列
题目描述
题意分析
求非空连续子数组的最大和，选择的元素必须相邻，全为负数时也要保留至少一个元素。先用滚动状态在线性时间内求解，再给出题目进阶要求的分治合并方法。
解法：Kadane 维护以当前位置结尾的最大和
核心思路
[!blue]
cur表示必须以当前下标结尾的最大连续和，ans表示已经扫描过的所有结尾中的最大值。处理nums[i]时，合法连续段只有两类：只选当前元素，或者把它接在以i - 1结尾的连续段后。后一类只需保留此前最大的cur，更小的旧段加上同一个元素也不会更优。因此新状态是
max(nums[i], oldCur + nums[i])。旧cur < 0时，接上它会拖低当前元素，应从当前位置重新开始；旧cur >= 0时，续接至少不会变差。两种情况都仍以当前元素结尾，不会把不相邻的元素拼在一起。每个连续子数组都有一个右端点，扫描所有结尾并更新
ans就覆盖了全部答案。两个状态都从首元素初始化，可以正确处理单元素和全负数组；若把全局答案设为 0，就会错误允许空子数组。
解题步骤
- cur 和 ans 都用首元素初始化。
- 从第二个元素扫描，旧 cur 为负则重启，否则累加。
- 每次用 cur 更新全局最大值。
代码实现
class Solution {
public int maxSubArray(int[] nums) {
int cur = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
// cur 表示必须以当前位置结尾的最大连续和。
if (cur < 0) {
cur = nums[i];
} else {
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++ {
// cur 表示必须以当前位置结尾的最大连续和。
if cur < 0 {
cur = nums[i]
} else {
cur += nums[i]
}
if cur > ans {
ans = cur
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素只更新一次状态。
- 空间复杂度：额外空间 $O(1)$，只保存当前结尾与全局两个最大值。
关键点总结
[!green]
局部状态必须包含当前位置，全局状态才允许在所有结尾中选择。是否重启由旧段的总和决定，而不是只看当前元素的正负。
解法：分治合并区间信息
核心思路
[!blue]
将区间分成左右两半。最优连续段要么完全在左半，要么完全在右半，要么跨过中点。跨中点的连续段必须由“左半的一个后缀”和“右半的一个前缀”拼接，因此左右各自的最大子段和还不够，需要同时返回边界信息。
每个区间返回四项，代码按下标 0 到 3 保存：区间总和
sum、非空最大前缀和prefix、非空最大后缀和suffix、非空最大子段和best。单元素区间的四项都等于该元素。合并时，总和为左右总和之和。最大前缀要么只在左半，要么取完左半再接右半前缀，所以是
max(left.prefix, left.sum + right.prefix)；最大后缀对称地为max(right.suffix, right.sum + left.suffix)。最大子段和则取left.best、right.best、left.suffix + right.prefix三者最大值。四项信息在常数时间内合并，递归到整段就得到答案。所有前缀、后缀和子段都要求非空，因此叶子不能把负数改成 0。区间总和可能超出 32 位，即使最终最大和仍能表示，合并信息也使用 64 位整数，最后按题目接口返回结果。
解题步骤
- 用闭区间
[lo, hi]递归，单元素时返回由该元素组成的四项状态。- 在中点处分成
[lo, mid]与[mid + 1, hi]，分别获得左右状态。- 按总和、前缀、后缀、最大子段的公式合并并返回。
- 整个数组的状态下标 3 就是最终答案。
代码实现
class Solution {
public int maxSubArray(int[] nums) {
return (int) divide(nums, 0, nums.length - 1)[3];
}
private long[] divide(int[] nums, int lo, int hi) {
if (lo == hi) {
return new long[] {
nums[lo],
nums[lo],
nums[lo],
nums[lo]
};
}
int mid = lo + (hi - lo) / 2;
long[] left = divide(nums, lo, mid);
long[] right = divide(nums, mid + 1, hi);
return new long[] {
left[0] + right[0],
Math.max(left[1], left[0] + right[1]),
Math.max(right[2], right[0] + left[2]),
Math.max(Math.max(left[3], right[3]), left[2] + right[1])
};
}
}
func maxSubArray(nums []int) int {
var divide func(int, int) [4]int64
divide = func(lo int, hi int) [4]int64 {
if lo == hi {
value := int64(nums[lo])
return [4]int64{
value,
value,
value,
value,
}
}
mid := lo + (hi-lo)/2
left := divide(lo, mid)
right := divide(mid+1, hi)
return [4]int64{
left[0] + right[0],
max(left[1], left[0]+right[1]),
max(right[2], right[0]+left[2]),
max(left[3], right[3], left[2]+right[1]),
}
}
return int(divide(0, len(nums)-1)[3])
}
复杂度分析
- 时间复杂度：$O(n)$。每个叶子对应一个元素，递归树中每个节点只做常数次合并。
- 空间复杂度：$O(\log n)$ 辅助空间，来自平衡递归栈及每层保留的常数项区间状态。
关键点总结
[!green]
只记录子区间最优值无法计算跨边界答案；总和、最大前缀与最大后缀使区间能够独立合并。四项都按非空区间定义，才能保留全负数组的正确结果。
易错点总结
[!yellow]
- 不能把 ans 初始化为0，否则全负数组会错误选择空子数组。
- 不能把非连续元素拼接成本题答案。
- 全量前缀和即使在答案可用int表示时也可能溢出，因此这里保留不累加负前缀的滚动主解。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 918. 环形子数组的最大和 | 中等 | 同样复用最大连续和，环形版本还要比较跨首尾的总和减最小子段。 |
| 152. 乘积最大子数组 | 中等 | 同样维护以当前位置结尾的状态，乘积遇负数会交换大小，需同时保存最大与最小值。 |