来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays
给你一个整数数组 nums 和一个整数 k ,找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组,并返回这三个子数组。
以下标的数组形式返回结果,数组中的每一项分别指示每个子数组的起始位置(下标从 0 开始)。如果有多个结果,返回字典序最小的一个。
示例 1:
输入:nums = [1,2,1,2,6,7,5,1], k = 2 输出:[0,3,5] 解释:子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
示例 2:
输入:nums = [1,2,1,2,1,2,1,2,1], k = 2 输出:[0,2,4]
提示:
1 <= nums.length <= 2 * 104 1 <= nums[i] < 216 1 <= k <= floor(nums.length / 3)
同时向右滑动这三个窗口,维护 maxSum_{12}及其对应位置。每次滑动时,计算当前 maxSum_{12} 与{sum}_3 之和。统计这一过程中{maxSum}_{12} +{sum}_3 的最大值及其对应位置。
对于题目要求的最小字典序,由于是从左向右遍历的,并且仅当元素和超过最大元素和时才修改最大元素和,从而保证求出来的下标列表是字典序最小的。
class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
ans = []
sum1, maxSum1, maxSum1Idx = 0, 0, 0
sum2, maxSum12, maxSum12Idx = 0, 0, ()
sum3, maxTotal = 0, 0
for i in range(k * 2, len(nums)):
sum1 += nums[i - k * 2]
sum2 += nums[i - k]
sum3 += nums[i]
if i >= k * 3 - 1:
if sum1 > maxSum1:
maxSum1 = sum1
maxSum1Idx = i - k * 3 + 1
if maxSum1 + sum2 > maxSum12:
maxSum12 = maxSum1 + sum2
maxSum12Idx = (maxSum1Idx, i - k * 2 + 1)
if maxSum12 + sum3 > maxTotal:
maxTotal = maxSum12 + sum3
ans = [*maxSum12Idx, i - k + 1]
sum1 -= nums[i - k * 3 + 1]
sum2 -= nums[i - k * 2 + 1]
sum3 -= nums[i - k + 1]
return ans
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
vector<int> ans;
int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
int sum3 = 0, maxTotal = 0;
for (int i = k * 2; i < nums.size(); ++i) {
sum1 += nums[i - k * 2];
sum2 += nums[i - k];
sum3 += nums[i];
if (i >= k * 3 - 1) {
if (sum1 > maxSum1) {
maxSum1 = sum1;
maxSum1Idx = i - k * 3 + 1;
}
if (maxSum1 + sum2 > maxSum12) {
maxSum12 = maxSum1 + sum2;
maxSum12Idx1 = maxSum1Idx;
maxSum12Idx2 = i - k * 2 + 1;
}
if (maxSum12 + sum3 > maxTotal) {
maxTotal = maxSum12 + sum3;
ans = {maxSum12Idx1, maxSum12Idx2, i - k + 1};
}
sum1 -= nums[i - k * 3 + 1];
sum2 -= nums[i - k * 2 + 1];
sum3 -= nums[i - k + 1];
}
}
return ans;
}
};