题目描述
给定数组 nums
由正整数组成,找到三个互不重叠的子数组的最大和。
每个子数组的长度为 k
,我们要使这 3*k
个项的和最大化。
返回每个区间起始索引的列表(索引从 0 开始)。如果有多个结果,返回字典序最小的一个。
样例
输入: [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
(线性遍历) $O(n)$
- 将
nums
数组变为sum
数组,其中 $sum(i) = \sum_{j = i}^{i + k - 1}{nums(j)}$,即sum
数组的每一项都是nums
数组中对应k
项的和。 - 题目可以转化为,在
sum
数组中取三个位置x, y, z
,满足 $x + k <= y$ 且 $y + k <= z$。 - 对
sum
数组,求前缀最大值数组l
,以及后缀最大值数组r
。l[i]
表示sum
数组中前i
个数字的最大值的位置,r[i]
表示sum
数组中第i
个到末尾最大值的位置。如果最大值相同,则取位置靠前的。 - 从
k
到n - k - k
枚举中间的数字的位置y
。对于每个位置i
,如果sum[l[i - k]] + sum[i] + sum[r[i + k]]
比答案大,则更新答案。如果和答案一致,则比较x
的字典序然后更新答案。
时间复杂度
- 每个位置仅遍历常数次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外三个数组,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> sum(n - k + 1);
int t = 0;
for (int i = 0; i < k - 1; i++)
t += nums[i];
for (int i = k - 1; i < n; i++) {
t += nums[i];
sum[i - k + 1] = t;
t -= nums[i - k + 1];
}
vector<int> l(n - k + 1), r(n - k + 1);
l[0] = 0;
for (int i = 1; i < n - k + 1; i++)
if (sum[l[i - 1]] >= sum[i]) {
l[i] = l[i - 1];
} else {
l[i] = i;
}
r[n - k] = n - k;
for (int i = n - k - 1; i >= 0; i--)
if (sum[r[i + 1]] > sum[i]) {
r[i] = r[i + 1];
} else {
r[i] = i;
}
int x, y, z, ans = 0;
for (int i = k; i < n - k + 1 - k; i++)
if (ans < sum[l[i - k]] + sum[i] + sum[r[i + k]]) {
ans = sum[l[i - k]] + sum[i] + sum[r[i + k]];
x = l[i - k];
y = i;
z = r[i + k];
} else if (ans == sum[l[i - k]] + sum[i] + sum[r[i + k]]) {
if (x > l[i - k]) {
x = l[i - k];
y = i;
z = r[i + k];
}
}
return {x, y, z};
}
};
算法2
(动态规划) $O(n)$
- 设 $f(i, j)$ 表示前 $i$ 个数字,选 $j$ 个不重叠的子数组的最大值。注意这里有效位置的下标都从 1 开始。
- 初始值,$f(i, 0) = 0$,其余为负无穷。
- 转移时,可以不选以这个位置结尾的子数组,即 $f(i, j) = f(i - 1, j)$;如果选,则 $f(i, j) = f(i - k, j - 1) + sum(i) - sum(i - k)$。二者取最大值,其中
sum
数组为前缀和数组。 - 最终答案为 $f(n, 3)$。
- 但此题要求输出字典序最小的答案,如果按照正序动态规划的方法,无法找到字典序最小的,只能找到字典序最大的(最靠后的,因为找方案需要从后向前回溯),故我们将原数组做一个翻转。
- 找方案的过程很经典,根据动态规划的过程进行倒推。初始时,$i = n, j = 3$,如果 $f(i - 1, j) > f(i - k, j - 1) + sum(i) - sum(i - k)$,则 $i = i - 1$;否则,我们就取当前的 $i$ 作为一个位置,然后更新 $i = i - k, j = j - 1$,继续以上的流程。
- 这种方法可以拓展到选 $m$ 个不重叠的子数组。
时间复杂度
- 动态规划的状态数为 $O(n)$,转移的时间复杂度为常数,故时间复杂度为 $O(n)$。
- 找方案的时间复杂度不会超过动态规划的时间,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要额外 $O(n)$ 的空间存储前缀和数组和动态规划的状态。
C++ 代码
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> sum(n + 1, 0);
reverse(nums.begin(), nums.end());
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + nums[i - 1];
vector<vector<int>> f(n + 1, vector<int>(4, INT_MIN));
for (int i = 0; i <= n; i++)
f[i][0] = 0;
for (int i = k; i <= n; i++)
for (int j = 1; j <= 3; j++)
f[i][j] = max(f[i - 1][j], f[i - k][j - 1] + sum[i] - sum[i - k]);
int i = n, j = 3;
vector<int> ans;
while (j > 0) {
if (f[i - 1][j] > f[i - k][j - 1] + sum[i] - sum[i - k]) {
i--;
} else {
ans.push_back(n - i);
i -= k;
j--;
}
}
return ans;
}
};