689. Maximum Sum of 3 Non-Overlapping Subarrays
Problem Description
Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum. 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.
Examples:
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 that would be a lexicographically larger solution.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2,1], k = 2 Output: [0,2,4]
Constraints:
- 1 ≤ nums.length ≤ 2 * 104
- 1 ≤ nums[i] ≤ 105
- 1 ≤ k ≤ floor(nums.length/3)
Python Solution
class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
# Calculate window sums
window_sums = []
curr_sum = sum(nums[:k])
window_sums.append(curr_sum)
for i in range(k, len(nums)):
curr_sum = curr_sum - nums[i-k] + nums[i]
window_sums.append(curr_sum)
# Calculate left max indices
left = [0] * len(window_sums)
best = 0
for i in range(len(window_sums)):
if window_sums[i] > window_sums[best]:
best = i
left[i] = best
# Calculate right max indices
right = [0] * len(window_sums)
best = len(window_sums) - 1
for i in range(len(window_sums)-1, -1, -1):
if windowSums[i] >= windowSums[best]:
best = i
right[i] = best
# Find the best combination
ans = [-1, -1, -1]
max_sum = 0
for i in range(k, len(nums)-2*k+1):
left_idx = left[i-k]
right_idx = right[i+k]
total = window_sums[left_idx] + window_sums[i] + window_sums[right_idx]
if total > max_sum:
max_sum = total
ans = [left_idx, i, right_idx]
return ansImplementation Notes:
- Uses sliding window to calculate window sums
- Maintains left and right max indices arrays
- Time complexity: O(n)
- Space complexity: O(n)
Java Solution
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] windowSums = new int[n - k + 1];
int currSum = 0;
// Calculate window sums
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
windowSums[0] = currSum;
for (int i = k; i < n; i++) {
currSum = currSum - nums[i-k] + nums[i];
windowSums[i-k+1] = currSum;
}
// Calculate left max indices
int[] left = new int[windowSums.length];
int best = 0;
for (int i = 0; i < windowSums.length; i++) {
if (windowSums[i] > windowSums[best]) {
best = i;
}
left[i] = best;
}
// Calculate right max indices
int[] right = new int[windowSums.length];
best = windowSums.length - 1;
for (int i = windowSums.length - 1; i >= 0; i--) {
if (windowSums[i] >= windowSums[best]) {
best = i;
}
right[i] = best;
}
// Find the best combination
int[] ans = new int[]{-1, -1, -1};
int maxSum = 0;
for (int i = k; i < n - 2*k + 1; i++) {
int leftIdx = left[i-k];
int rightIdx = right[i+k];
int total = windowSums[leftIdx] + windowSums[i] + windowSums[rightIdx];
if (total > maxSum) {
maxSum = total;
ans = new int[]{leftIdx, i, rightIdx};
}
}
return ans;
}
}C++ Solution
class Solution {
public:
vector maxSumOfThreeSubarrays(vector& nums, int k) {
int n = nums.size();
vector windowSums(n - k + 1);
int currSum = 0;
// Calculate window sums
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
windowSums[0] = currSum;
for (int i = k; i < n; i++) {
currSum = currSum - nums[i-k] + nums[i];
windowSums[i-k+1] = currSum;
}
// Calculate left max indices
vector left(windowSums.size());
int best = 0;
for (int i = 0; i < windowSums.size(); i++) {
if (windowSums[i] > windowSums[best]) {
best = i;
}
left[i] = best;
}
// Calculate right max indices
vector right(windowSums.size());
best = windowSums.size() - 1;
for (int i = windowSums.size() - 1; i >= 0; i--) {
if (windowSums[i] >= windowSums[best]) {
best = i;
}
right[i] = best;
}
// Find the best combination
vector ans = {-1, -1, -1};
int maxSum = 0;
for (int i = k; i < n - 2*k + 1; i++) {
int leftIdx = left[i-k];
int rightIdx = right[i+k];
int total = windowSums[leftIdx] + windowSums[i] + windowSums[rightIdx];
if (total > maxSum) {
maxSum = total;
ans = {leftIdx, i, rightIdx};
}
}
return ans;
}
}; JavaScript Solution
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSumOfThreeSubarrays = function(nums, k) {
const n = nums.length;
const windowSums = new Array(n - k + 1);
let currSum = 0;
// Calculate window sums
for (let i = 0; i < k; i++) {
currSum += nums[i];
}
windowSums[0] = currSum;
for (let i = k; i < n; i++) {
currSum = currSum - nums[i-k] + nums[i];
windowSums[i-k+1] = currSum;
}
// Calculate left max indices
const left = new Array(windowSums.length);
let best = 0;
for (let i = 0; i < windowSums.length; i++) {
if (windowSums[i] > windowSums[best]) {
best = i;
}
left[i] = best;
}
// Calculate right max indices
const right = new Array(windowSums.length);
best = windowSums.length - 1;
for (let i = windowSums.length - 1; i >= 0; i--) {
if (windowSums[i] >= windowSums[best]) {
best = i;
}
right[i] = best;
}
// Find the best combination
const ans = [-1, -1, -1];
let maxSum = 0;
for (let i = k; i < n - 2*k + 1; i++) {
const leftIdx = left[i-k];
const rightIdx = right[i+k];
const total = windowSums[leftIdx] + windowSums[i] + windowSums[rightIdx];
if (total > maxSum) {
maxSum = total;
ans[0] = leftIdx;
ans[1] = i;
ans[2] = rightIdx;
}
}
return ans;
};C# Solution
public class Solution {
public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.Length;
int[] windowSums = new int[n - k + 1];
int currSum = 0;
// Calculate window sums
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
windowSums[0] = currSum;
for (int i = k; i < n; i++) {
currSum = currSum - nums[i-k] + nums[i];
windowSums[i-k+1] = currSum;
}
// Calculate left max indices
int[] left = new int[windowSums.Length];
int best = 0;
for (int i = 0; i < windowSums.Length; i++) {
if (windowSums[i] > windowSums[best]) {
best = i;
}
left[i] = best;
}
// Calculate right max indices
int[] right = new int[windowSums.Length];
best = windowSums.Length - 1;
for (int i = windowSums.Length - 1; i >= 0; i--) {
if (windowSums[i] >= windowSums[best]) {
best = i;
}
right[i] = best;
}
// Find the best combination
int[] ans = new int[]{-1, -1, -1};
int maxSum = 0;
for (int i = k; i < n - 2*k + 1; i++) {
int leftIdx = left[i-k];
int rightIdx = right[i+k];
int total = windowSums[leftIdx] + windowSums[i] + windowSums[rightIdx];
if (total > maxSum) {
maxSum = total;
ans = new int[]{leftIdx, i, rightIdx};
}
}
return ans;
}
}Implementation Notes:
- Uses sliding window technique to calculate window sums
- Maintains arrays for left and right maximum indices
- Returns lexicographically smallest answer when multiple solutions exist
- Time complexity: O(n)
- Space complexity: O(n)