LeetCode 补充题 155. 最大子数组和及其起点
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 53. 最大子数组和
:::
给定非空整数数组
nums，返回最大非空连续子数组的和，以及该子数组在原数组中的起始下标。若存在多个最大和区间，返回其中任意一个的起点即可。
示例 1：
输入：
nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：sum = 6, start = 3
解释： 从下标 3 开始的[4,-1,2,1]的和为 6。
示例 2：
输入：
nums = [-4,-2,-7]
输出：sum = -2, start = 1
解释： 必须选择非空区间，全负数时选最大的单个元素。
提示：
- 下标从
0开始。 - 元素可以为负数，和使用
64位整数。 - 返回对象包含
sum、start两个字段。
题意分析
任意最优连续区间都以某个位置结尾。若能维护每个位置结尾的最大和，再取这些状态的最大值，就覆盖了全局答案；额外保存该状态的起点即可返回所需下标。
解法：Kadane 同步维护起点
核心思路
[!blue]
ending表示以上一位置结尾的最大非空区间和，start是它的起点。加入当前元素时，只能选择延长这段区间，或丢弃全部前缀、从当前元素重新开始。若旧
ending < 0，保留它一定比单独取当前元素更差，因此同时重置ending和start；否则延长原区间。出现严格更大的全局和时，再同步保存best、bestStart，局部起点与全局起点不能混用。用首元素初始化保证所选区间非空，全负数组也能得到最大的单个值。累计和使用 64 位；同和时保留旧答案符合任意起点的要求。
解题步骤
- 用首元素初始化当前段和与全局最大和，起点均为 0。
- 上一段和为负就从当前位置重新开始，否则继续延长。
- 出现严格更大的总和时记录当前起点。
代码实现
class Solution {
static class Result {
final long sum;
final int start;
Result(long sum, int start) {
this.sum = sum;
this.start = start;
}
}
public Result maxSumStart(int[] nums) {
long ending = nums[0];
long best = ending;
int start = 0;
int bestStart = 0;
for (int i = 1; i < nums.length; i++) {
if (ending < 0) {
ending = nums[i];
start = i;
} else {
ending += nums[i];
}
if (ending > best) {
best = ending;
bestStart = start;
}
}
return new Result(best, bestStart);
}
}
type SumStart struct {
Sum int64
Start int
}
func maxSumStart(nums []int) SumStart {
ending := int64(nums[0])
best := ending
start, bestStart := 0, 0
for i := 1; i < len(nums); i++ {
if ending < 0 {
ending = int64(nums[i])
start = i
} else {
ending += int64(nums[i])
}
if ending > best {
best = ending
bestStart = start
}
}
return SumStart{best, bestStart}
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
当前段状态与其起点必须一起更新；和为 0 时继续延长，配合严格更新全局答案保留较早起点。
易错点总结
[!yellow]
起点与当前段同步更新；不能把全局最大值初始化为 0，否则全负数会错。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 在最大连续子数组和的状态上同时维护起点，并用严格更新保留更早的同分起点。 |
| 918. 环形子数组的最大和 | 中等 | 同样以 Kadane 状态为基础，环形版本还需考虑跨数组首尾的段，本题仅返回普通线性段起点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！