LeetCode 1031. 两个无重叠子数组的最大和
目录
题目描述
题意分析
从数组里挑出两段连续区间，长度分别固定为
firstLen和secondLen，两段不能有任何重叠，求两段元素之和的最大值。有两个容易读漏的点。第一，长度是固定的，不是「不超过」，所以每一段的和只由它的起点决定，可选位置总共只有 $O(n)$ 个。第二，题目没有规定哪一段必须排在前面，
firstLen那段可以在左也可以在右，两种情况都要考虑。「不重叠」的精确含义是两段的下标区间交集为空，中间可以隔任意多个元素，也可以首尾紧挨着，但绝不能共用哪怕一个下标。
约束里保证了
firstLen + secondLen <= nums.length，所以一定存在合法解，不必处理无解情况；元素都是非负数，这让「初值取 0」是安全的，换成允许负数的变体就必须改成负无穷。
解法：前缀和 + 前缀最优
核心思路
前缀和先解决「区间求和」：令
prefix[i]表示前i个元素之和，则半开区间[l, r)的和为prefix[r] - prefix[l]，可以在 $O(1)$ 时间得到。难点是同时选择两个区间。任意两个不重叠区间必然满足一种相对顺序：要么长度为
firstLen的区间在左，要么长度为secondLen的区间在左。因此分别计算这两种顺序，再取最大值，就不会漏解。固定「长度为
leftLen的区间在左」后，从左到右枚举右区间起点rightStart。边界每右移一格，只会新增一个可放在左侧的区间[rightStart-leftLen, rightStart)，用bestLeft维护所有已合法左区间的最大和即可。扫描不变量是：更新完成后，
bestLeft等于所有「长度为leftLen且右端点不超过rightStart」区间的最大和。因此bestLeft + 右区间和就是当前rightStart下的最优组合。正确性来自两点：代码产生的左区间都在
rightStart之前，候选解一定不重叠；反过来，任取一组最优解，较右区间的起点被枚举到时，较左区间已经包含在bestLeft的候选集合中。两种相对顺序都计算后，全局最优解必然被覆盖。
解题步骤
- 构造长度为
n + 1的前缀和数组，统一使用左闭右开的区间语义。- 调用两次
maxWithOrder：先计算firstLen在左，再计算secondLen在左。- 对固定顺序，从
rightStart = leftLen开始枚举，直到右区间仍能完整放入数组。- 每轮先计算新出现的左区间
[rightStart-leftLen, rightStart)，更新bestLeft。- 再计算右区间
[rightStart, rightStart+rightLen)，用两段之和更新答案。- 返回两种顺序答案的较大值。
例如
nums = [0,6,5,2,2,5,1,9,4]、firstLen = 1、secondLen = 2。在「长度 2 的区间在左」这次扫描中，当右区间起点到达下标 7 时，bestLeft已记录区间[1,3)的和 11，当前长度 1 的右区间和为 9，得到 20。即使两段中间有空隙，历史最大值也不会丢失这个组合。
代码实现
class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
return Math.max(
maxWithOrder(prefix, firstLen, secondLen),
maxWithOrder(prefix, secondLen, firstLen)
);
}
private int maxWithOrder(int[] prefix, int leftLen, int rightLen) {
int n = prefix.length - 1;
int bestLeft = 0;
int answer = 0;
for (int rightStart = leftLen; rightStart + rightLen <= n; rightStart++) {
int leftSum = prefix[rightStart] - prefix[rightStart - leftLen];
bestLeft = Math.max(bestLeft, leftSum);
int rightSum = prefix[rightStart + rightLen] - prefix[rightStart];
answer = Math.max(answer, bestLeft + rightSum);
}
return answer;
}
}
func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) int {
prefix := make([]int, len(nums)+1)
for i, num := range nums {
prefix[i+1] = prefix[i] + num
}
firstBeforeSecond := maxWithOrder(prefix, firstLen, secondLen)
secondBeforeFirst := maxWithOrder(prefix, secondLen, firstLen)
if firstBeforeSecond > secondBeforeFirst {
return firstBeforeSecond
}
return secondBeforeFirst
}
func maxWithOrder(prefix []int, leftLen int, rightLen int) int {
n := len(prefix) - 1
bestLeft, answer := 0, 0
for rightStart := leftLen; rightStart+rightLen <= n; rightStart++ {
leftSum := prefix[rightStart] - prefix[rightStart-leftLen]
if leftSum > bestLeft {
bestLeft = leftSum
}
rightSum := prefix[rightStart+rightLen] - prefix[rightStart]
if bestLeft+rightSum > answer {
answer = bestLeft + rightSum
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。构造前缀和一次，两种顺序各扫描一次；常数次线性扫描仍是 $O(n)$。
- 空间复杂度：$O(n)$，用于保存前缀和数组。
关键点总结
- 不重叠的两个区间只有两种相对顺序，分别求解即可完整覆盖答案空间。
- 固定顺序后，右区间起点是分界线；
bestLeft保存分界线左侧的最优定长区间。bestLeft必须是历史最大值，而不是只取紧挨右区间的那一段，因为最优两段之间允许有空隙。- 半开区间让「左区间右端点等于右区间起点」自然表示相邻但不重叠。
- 面试时要能用「候选始终合法 + 任意最优解都会被枚举」两句话完成正确性证明。
易错点总结
- 只计算一种顺序：
[0,6,5,2,2,5,1,9,4]、长度 1 和 2 的答案是 20，只算长度 1 在左会漏掉长度 2 在左的最优组合。- 不维护历史最大值：若只取紧贴右区间的左段，
[9,0,0,9,9]、长度 1 和 2 会得到 18，而正确答案是 27。- 先算了与右区间重叠的左段：左段最晚只能结束在
rightStart，区间应为[rightStart-leftLen, rightStart)。- 循环边界少写等号：条件必须允许
rightStart + rightLen == n，否则会漏掉以数组末尾结尾的右区间。- 前缀和下标混用开闭区间：牢记
prefix[i]表示前i个元素，[l, r)的和才是prefix[r] - prefix[l]。- 照搬到含负数的变体：本题元素非负，所以初值为 0 安全；若允许负数，
bestLeft和答案都应初始化为足够小的值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 长度不固定的单段最大和，用 Kadide 式滚动状态 |
| 303. 区域和检索 - 数组不可变 | 简单 | 只练前缀和的构建与下标语义，无需任何决策 |
| 643. 子数组最大平均数 I | 简单 | 单段定长最大和，定长窗口的最小模板 |
| 689. 三个无重叠子数组的最大和 | 困难 | 段数升到 3 且要输出下标，顺序枚举失效，改用分段 DP |