题目描述
给定数组 nums
由正整数组成,找到三个互不重叠的子数组的最大和。
每个子数组的长度为k
,我们要使这3*k
个项的和最大化。
返回每个区间起始索引的列表(索引从 0
开始)。如果有多个结果,返回字典序最小的一个。
样例1
输入: [1,2,1,2,6,7,5,1], 2
输出: [0, 3, 5]
解释: 子数组 [1, 2], [2, 6], [7, 5] 对应的起始索引为 [0, 3, 5]。
我们也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
提示
nums.length
的范围在[1, 20000]
之间。nums[i]
的范围在[1, 65535]
之间。k
的范围在[1, floor(nums.length / 3)]
之间。
算法1
(预处理 + 线性扫描)
- 预处理一个
sum
数组记录每个长度为k
的区间和,问题可以转换为在sum
中找到三个下标i
,j
,u
,使得i + k <= j, j + k <= u
(区间互不重叠),且sum[i] + sum[j] + sum[u]
最大,且三元组{i, j, u}
字典序最小 - 预处理
l
和r
,l[i]
表示i
左侧最大的sum
下标,r[i]
表示i
右侧最大的sum
下标;为保证字典序最小,左侧如果有多个相同值,取最左侧的,右侧如果有多个相同值,也取最左侧的 -
枚举第二个区间的
sum
下标i
,范围在[k, n-k]
内,答案就是sum[i-k] + sum[i] + sum[i+k]
取最大即可 -
时间复杂度:$O(n)$
Java 代码
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
// 预处理每k个元素的区间和
int[] sum = new int[n-k+1];
int s = 0, u = 0;
for(int i = 0; i < k; i++){
s += nums[i];
}
sum[u++] = s;
for(int i = k; i < n; i++){
s += nums[i] - nums[i-k];
sum[u++] = s;
}
int m = sum.length;
// l[i]: i及其左侧sum最大的值下标
int[] l = new int[m];
// r[i]: i及其右侧sum最大的值下标
int[] r = new int[m];
l[0] = 0; r[m-1] = m-1;
for(int i = 1; i < m; i++){
// 左侧如果多个相同取最左边的
if(sum[i] > sum[l[i-1]]) l[i] = i;
else l[i] = l[i-1];
}
for(int i = m-2; i >= 0; i--){
// 右侧如果多个相同取最左边的
if(sum[i] >= sum[r[i+1]]) r[i] = i;
else r[i] = r[i+1];
}
int maxv = 0;
int[] res = new int[3];
// 枚举中间段的起点
for(int i = k; i + k < m; i++){
if(maxv < sum[l[i-k]] + sum[i] + sum[r[i+k]]){
maxv = sum[l[i-k]] + sum[i] + sum[r[i+k]];
res[0] = l[i-k];
res[1] = i;
res[2] = r[i+k];
}
}
return res;
}
}
算法2
(前缀和 + 动态规划 + 反推方案)
- 此方法可以推广到:把数组划分为
m
个重叠子数组的最大和 - 状态定义:
f[i][j]
表示前i
个元素中,划分出j
个子数组的最大和,答案记为f[n][3]
- 状态转移:对于第
i
个数,可以选或不选:选了则必须选择[i-k, i]
范围内的所有数,利用前缀和快速获得选取的区间和,满足f[i][j] = max(f[i-1][j], f[i-k][j-1] + s[i] - s[i-k])
- 由于从
f[n][3]
往回推方案会获得字典序最大的方案,考虑一开始将数组进行反转再进行动态规划,这样可以得到字典序最小的方案,其中反转后的下标对应原数组的下标n - i
-
从后往前考虑每个区间,如果划分位置
i-k
满足f[i][j] > f[i-k][j-1] + s[i] - s[i-k]
,说明当前的划分位置会导致得不到最优解,所以不应该在此处划分,i
向前移动一位,直到推出最后一个区间的位置 -
时间复杂度:$O(n)$
Java代码
- 用数组做标记
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
for(int i = 0, j = n-1; i < j; i++, j--){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
int[][] f = new int[n+1][4];
int[] s = new int[n+1];
for(int i = 1; i <= n; i++){
s[i] = s[i-1] + nums[i-1];
}
for(int i = k; i <= n; i++){
for(int j = 1; j <= 3; j++){
f[i][j] = Math.max(f[i-1][j], f[i-k][j-1] + s[i] - s[i-k]);
}
}
int i = n, j = 3, u = 0;
int[] res = new int[3];
while(j > 0){
if(f[i][j] > f[i-k][j-1] + s[i] - s[i-k]) i--;
else if(f[i][j] == f[i-k][j-1] + s[i] - s[i-k]){
res[u++] = n - i;
i -= k;
j--;
}
}
return res;
}
}