LeetCode 689. 三个无重叠子数组的最大和
题目描述
题意分析
选择三个长度都为
k、互不重叠的子数组，使总和最大，返回从左到右排列的三个起始下标。总和相同时，需要返回字典序最小的下标组合。直接枚举三个窗口太慢。固定中间窗口以后，左窗口只能出现在它左侧，右窗口只能出现在它右侧，两边可以独立选取最大窗口和，因此只需预处理每个前缀、后缀里的最优窗口。
解法：窗口和 + 两侧最优预处理
核心思路
[!blue]
先用滑动窗口得到
sums[i]，表示从i开始、长度为k的子数组和。共有n-k+1个窗口；移动起点时，减去离开的左端元素，加上新进入的右端元素即可。
left[i]保存起点在0..i中的最大和窗口起点，平局选更小下标；right[i]保存起点在i..n-k中的最大和窗口起点，同样平局选更小下标。正向构造left时，旧候选下标更小，所以只在新窗口和严格更大时更新；反向构造right时，当前下标更小，所以相等时也要更新。设中间窗口起点为
j。为了不重叠，左窗口起点最多是j-k，右窗口起点至少是j+k，于是取l = left[j-k]、r = right[j+k]。两侧选择都已与中间隔开，也就不会彼此重叠；各取最大和能得到固定j下的最大总和。枚举k <= j <= n-2k就能覆盖所有合法中间位置。最终答案也要正确处理平局。中间位置
j按升序枚举，而left[j-k]只会保持不变或更新为更靠右的起点，绝不会变小。因此两个总和相同的候选中，先遇到的左起点不大于后者；左起点相同时，先遇到的中间起点更小，所以先遇到的组合字典序一定更小。只在总和严格增大时更新答案即可。对同一个中间位置，两侧表又已经分别保留最小的最优起点，尤其在左、中起点固定后，右表保证第三个下标最小。三处平局规则合在一起，才保证完整答案的字典序。
解题步骤
- 计算全部长度为
k的窗口和。- 从左到右建立前缀最优起点表，只在窗口和严格更大时替换候选。
- 从右到左建立后缀最优起点表，窗口和大于或等于旧候选时都替换。
- 升序枚举中间起点
j，用left[j-k]和right[j+k]取得互不重叠的两侧窗口。- 三窗口总和严格超过当前最大值时保存三个零基起点；相等则保留已有答案。题目保证
3k <= n，至少存在一个合法组合。
代码实现
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] sums = new int[n - k + 1];
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
sums[0] = windowSum;
for (int i = 1; i <= n - k; i++) {
windowSum += nums[i + k - 1] - nums[i - 1];
sums[i] = windowSum;
}
int[] left = new int[sums.length];
int bestLeft = 0;
for (int i = 0; i < sums.length; i++) {
// 正向扫描遇到同和保留旧起点，保证左侧起点更小。
if (sums[i] > sums[bestLeft]) {
bestLeft = i;
}
left[i] = bestLeft;
}
int[] right = new int[sums.length];
int bestRight = sums.length - 1;
for (int i = sums.length - 1; i >= 0; i--) {
// 反向扫描遇到同和更新为当前起点，保证右侧起点更小。
if (sums[i] >= sums[bestRight]) {
bestRight = i;
}
right[i] = bestRight;
}
int[] answer = new int[] {
-1,
-1,
-1
};
int maxSum = -1;
for (int j = k; j + k < sums.length; j++) {
// 左右候选分别与中间窗口至少间隔一个窗口长度。
int l = left[j - k];
int r = right[j + k];
int total = sums[l] + sums[j] + sums[r];
if (total > maxSum) {
maxSum = total;
answer[0] = l;
answer[1] = j;
answer[2] = r;
}
}
return answer;
}
}
func maxSumOfThreeSubarrays(nums []int, k int) []int {
n := len(nums)
sums := make([]int, n-k+1)
windowSum := 0
for i := 0; i < k; i++ {
windowSum += nums[i]
}
sums[0] = windowSum
for i := 1; i <= n-k; i++ {
windowSum += nums[i+k-1] - nums[i-1]
sums[i] = windowSum
}
left := make([]int, len(sums))
bestLeft := 0
for i := 0; i < len(sums); i++ {
// 正向扫描遇到同和保留旧起点，保证左侧起点更小。
if sums[i] > sums[bestLeft] {
bestLeft = i
}
left[i] = bestLeft
}
right := make([]int, len(sums))
bestRight := len(sums) - 1
for i := len(sums) - 1; i >= 0; i-- {
// 反向扫描遇到同和更新为当前起点，保证右侧起点更小。
if sums[i] >= sums[bestRight] {
bestRight = i
}
right[i] = bestRight
}
result := []int{
-1,
-1,
-1,
}
maxSum := -1
for j := k; j+k < len(sums); j++ {
// 左右候选分别与中间窗口至少间隔一个窗口长度。
l := left[j-k]
r := right[j+k]
total := sums[l] + sums[j] + sums[r]
if total > maxSum {
maxSum = total
result[0] = l
result[1] = j
result[2] = r
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$。窗口和、左右最优表及中间位置枚举都只进行线性扫描。
- 空间复杂度：$O(n)$。保存窗口和以及左右最优起点数组，答案固定为三个下标。
关键点总结
[!green]
- 固定中间窗口后，两侧互不影响，分别取最大窗口和就是这一中间位置的最优解。
- 非重叠条件限制的是窗口起点：左端不超过
j-k，右端不小于j+k。- 左表使用严格大于、右表使用大于等于，都是为了在扫描方向不同的情况下保留更小起点。
- 中间起点升序、最优左起点不后退，使总和平局时保留旧答案可以保证整体字典序。
易错点总结
[!yellow]
- 直接取三个最大窗口，它们可能互相重叠，无法组成合法答案。
- 左表查到
j，或右表从j+1开始查，没有为中间窗口留出完整的k个位置。- 右表反向扫描只在严格更大时更新，会让平局候选停留在更靠右的位置。
- 左表同和时也更新，会把更小起点换成更大起点。
- 最终总和相等时覆盖答案，会丢掉先前字典序更小的组合。
maxSum = -1依赖题目中元素为正的范围；它能保证第一个合法组合一定写入答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1031. 两个无重叠子数组的最大和 | 中等 | 同样选择互不重叠的固定长度窗口，原题选两段，本题选三段并处理下标字典序。 |
| 1235. 规划兼职工作 | 困难 | 同样最大化不重叠区间收益，本题窗口等长且只选三段，可用左右最优数组简化通用区间DP。 |