Algorithm
Problem Name: 689. Maximum Sum of 3 Non-Overlapping Subarrays
Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
Example 1:
Input: nums = [1,2,1,2,6,7,5,1], k = 2 Output: [0,3,5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2,1], k = 2 Output: [0,2,4]
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] < 2161 <= k <= floor(nums.length / 3)
Code Examples
#1 Code Example with C Programming
Code -
C Programming
const maxSumOfThreeSubarrays = (nums, k) => {
let n = nums.length,
maxsum = 0
let sum = new Array(n + 1).fill(0),
posLeft = new Array(n).fill(0),
posRight = new Array(n).fill(0),
ans = new Array(3).fill(0)
for (let i = 0; i < n; i++) sum[i + 1] = sum[i] + nums[i]
for (let i = k, tot = sum[k] - sum[0]; i < n; i++) {
if (sum[i + 1] - sum[i + 1 - k] > tot) {
posLeft[i] = i + 1 - k
tot = sum[i + 1] - sum[i + 1 - k]
} else posLeft[i] = posLeft[i - 1]
}
posRight[n - k] = n - k
for (let i = n - k - 1, tot = sum[n] - sum[n - k]; i >= 0; i--) {
if (sum[i + k] - sum[i] >= tot) {
posRight[i] = i
tot = sum[i + k] - sum[i]
} else posRight[i] = posRight[i + 1]
}
for (let i = k; i < = n - 2 * k; i++) {
let l = posLeft[i - 1],
r = posRight[i + k]
let tot = sum[i + k] - sum[i] + (sum[l + k] - sum[l]) + (sum[r + k] - sum[r])
if (tot > maxsum) {
maxsum = tot
ans[0] = l
ans[1] = i
ans[2] = r
}
}
return ans
}
Input
nums = [1,2,1,2,6,7,5,1], k = 2
Output
[0,3,5]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
// dp[i] is the sum of subarray of in range [i , i + k)
// nextMax[i] is the maximum value in dp[i : dp.size() - 1]
// nextIdx[i] is the index of nextMax[i]
int n = nums.size(), sum = 0, maxRight = 0, idx = 0, maxSum = 0;
vector<int>res, dp(n - k + 1), nextMax(n - k + 1), nextIdx(n - k + 1);
// Using a sliding window to get the sum of subarray in range [i , i + k)
for(int i = 0; i < n; i++){
sum += nums[i];
if(i >= k) sum -= nums[i - k];
if(i >= k - 1) dp[i - k + 1] = sum;
}
// Starting from end of dp array to get the maximum value after current position
for(int i = dp.size() - 1; i >= 0; i--){
if(dp[i] > maxRight) maxRight = dp[i], idx = i;
nextMax[i] = maxRight;
nextIdx[i] = idx;
}
// Using two pointers i, j to find the result
// The third entry is determined by nextMax[j + k]
for(int i = 0; i <= n - 3 * k; i++)
for(int j = i + k; j < = n - 2 * k; j++>{
sum = dp[i] + dp[j] + nextMax[j + k];
if(sum > maxSum){
maxSum = sum;
res = {i, j, nextIdx[j + k]};
}
}
return res;
}
};
Input
nums = [1,2,1,2,6,7,5,1], k = 2
Output
[0,3,5]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const maxSumOfThreeSubarrays = (nums, k) => {
let n = nums.length,
maxsum = 0
let sum = new Array(n + 1).fill(0),
posLeft = new Array(n).fill(0),
posRight = new Array(n).fill(0),
ans = new Array(3).fill(0)
for (let i = 0; i < n; i++) sum[i + 1] = sum[i] + nums[i]
for (let i = k, tot = sum[k] - sum[0]; i < n; i++) {
if (sum[i + 1] - sum[i + 1 - k] > tot) {
posLeft[i] = i + 1 - k
tot = sum[i + 1] - sum[i + 1 - k]
} else posLeft[i] = posLeft[i - 1]
}
posRight[n - k] = n - k
for (let i = n - k - 1, tot = sum[n] - sum[n - k]; i >= 0; i--) {
if (sum[i + k] - sum[i] >= tot) {
posRight[i] = i
tot = sum[i + k] - sum[i]
} else posRight[i] = posRight[i + 1]
}
for (let i = k; i < = n - 2 * k; i++) {
let l = posLeft[i - 1],
r = posRight[i + k]
let tot = sum[i + k] - sum[i] + (sum[l + k] - sum[l]) + (sum[r + k] - sum[r])
if (tot > maxsum) {
maxsum = tot
ans[0] = l
ans[1] = i
ans[2] = r
}
}
return ans
}
Input
nums = [1,2,1,2,1,2,1,2,1], k = 2
Output
[0,2,4]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxSumOfThreeSubarrays(self, nums, k):
single, double, sm, n, cur = {}, {}, 0, len(nums), sum(nums[:k - 1])
for i in range(k - 1, n):
cur += nums[i]
single[i - k + 1] = cur
cur -= nums[i - k + 1]
cur = n - k, single[n - k]
for i in range(n - k, k * 2 - 1, -1):
if single[i] >= cur[1]:
cur = i, single[i]
double[i - k] = cur[1] + single[i - k], i - k, cur[0]
cur = double[n - 2 * k]
for i in range(n - 2 * k, k - 1, -1):
if double[i][0] >= cur[0]:
cur = double[i]
if single[i - k] + cur[0] >= sm:
sm, res = single[i - k] + cur[0], [i - k, cur[1], cur[2]]
return res
Input
nums = [1,2,1,2,1,2,1,2,1], k = 2
Output
[0,2,4]