Maximum Sum of 3 Non-Overlapping Subarrays solution and explanation
Google
9 more videos on this problem
Maximum Sum of 3 Non-Overlapping Subarrays - Leetcode 689 - PythonNeetCodeIO · 21:17 · 13K views
Maximum Sum of 3 Non-Overlapping Subarrays | Detailed For Beginners | Leetcode 689 | codstorywithMIKcodestorywithMIK · 48:45 · 13K views
LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays Explanation and Solutionhappygirlzt · 12:51 · 6K views
Maximum Sum of 3 Non Overlapping Subarrays | Leetcode 689Techdose · 24:00 · 6K views
689. Maximum Sum of 3 Non-Overlapping Subarrays | O(1) space | 2 Approaches | Sliding Window HardAryan Mittal · 41:34 · 3K views
LeetCode 689. Maximum Sum of 3 Non-Overlapping SubarraysHappy Coding · 24:04 · 3K views
Leetcode 689 Maximum Sum of 3 Non-Overlapping SubarraysRen Zhang · 27:58 · 3K views
689. Maximum Sum of 3 Non Overlapping Subarrays - English VersionSimple Code - 단순코드 · 17:39 · 993 views
689 Maximum Sum of 3 Non Overlapping SubarraysAmadeus Mozart · 23:14 · 899 views
LeetCode 689.Maximum Sum of 3 Non-Overlapping Subarrays | JSer - JavaScript & AlgorithmJSer · 36:42 · 645 views
The problem
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 smaller.
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)
Approach overview
Problem Overview: You are given an integer array and a fixed length k. The goal is to pick three non-overlapping subarrays of length k such that their total sum is maximized. The output should be the starting indices of those three subarrays in lexicographically smallest order when multiple answers exist.
Approach 1: Prefix Sum with Sliding Window (O(n) time, O(n) space)
This approach precomputes the sum of every subarray of length k using a sliding window. First build a prefix sum array so any window sum can be calculated in constant time. Then maintain two helper arrays: left[i] stores the index of the best window from the start up to i, and right[i] stores the best window from i to the end. Iterate through possible middle windows and combine it with the best left and right windows that do not overlap. Each step performs constant work, so the full scan runs in O(n) time with O(n) extra space.
The key insight is separating the problem into three windows where the middle window is fixed while the left and right sides reuse previously computed optimal windows. This removes the need to test all combinations and turns a potentially cubic search into a linear pass. This method relies heavily on techniques from Array processing and the Sliding Window pattern.
Approach 2: Dynamic Programming with Sliding Window (O(n) time, O(n) space)
Dynamic programming can model the problem as choosing up to three windows while maximizing total sum. Precompute all window sums using a sliding window. Then build a DP table where dp[i][j] represents the maximum sum using j windows considering the first i positions. For each position, either skip the current window or take it and add the value from dp[i-k][j-1]. Tracking decisions allows reconstruction of the starting indices.
This method generalizes easily if the number of subarrays changes from three to m. The transition uses previously computed states and avoids overlapping by jumping back k positions whenever a window is chosen. The algorithm still runs in O(n) time for the fixed case of three windows and uses O(n) memory. It demonstrates core ideas from Dynamic Programming combined with window preprocessing.
Recommended for interviews: The prefix sum + sliding window approach is what most interviewers expect. It shows you understand how to precompute window sums and reuse optimal substructure with helper arrays. Explaining the brute-force intuition first (checking all triples of windows) shows problem understanding, but the linear-time window optimization demonstrates strong algorithmic thinking.
Approach 1: Prefix Sum with Sliding Window
This approach uses a prefix sum array to quickly calculate the sum of any subarray and a sliding window technique to explore possible starting points for the subarrays.
def maxSumOfThreeSubarrays(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + nums[i - 1]
left = [0] * n
right = [0] * n
for i in range(k, n):
if prefix[i + 1] - prefix[i + 1 - k] > prefix[left[i - 1] + k] - prefix[left[i - 1]]:
left[i] = i + 1 - k
else:
left[i] = left[i - 1]
for i in range(n - k - 1, -1, -1):
if prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]:
right[i] = i
else:
right[i] = right[i + 1]
max_sum = 0
ans = [-1, -1, -1]
for mid in range(k, n - 2 * k + 1):
l, r = left[mid - 1], right[mid + k]
total_sum = (prefix[l + k] - prefix[l]) + (prefix[mid + k] - prefix[mid]) + (prefix[r + k] - prefix[r])
if total_sum > max_sum:
max_sum = total_sum
ans = [l, mid, r]
return ans
# Example usage
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
print(maxSumOfThreeSubarrays(nums, k))import java.util.Arrays;
public class Main {
public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int[] left = new int[n];
int[] right = new int[n];
for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
if (prefix[i + 1] - prefix[i + 1 - k] > total) {
left[i] = i + 1 - k;
total = prefix[i + 1] - prefix[i + 1 - k];
} else {
left[i] = left[i - 1];
}
}
for (int i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
if (prefix[i + k] - prefix[i] >= total) {
right[i] = i;
total = prefix[i + k] - prefix[i];
} else {
right[i] = right[i + 1];
}
}
int[] result = new int[3];
int maxSum = 0;
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = l;
result[1] = i;
result[2] = r;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
System.out.println(Arrays.toString(maxSumOfThreeSubarrays(nums, k)));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
vector<int> left(n, 0), right(n, n - k);
for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
if (prefix[i + 1] - prefix[i + 1 - k] > total) {
left[i] = i + 1 - k;
total = prefix[i + 1] - prefix[i + 1 - k];
} else {
left[i] = left[i - 1];
}
}
for (int i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
if (prefix[i + k] - prefix[i] >= total) {
right[i] = i;
total = prefix[i + k] - prefix[i];
} else {
right[i] = right[i + 1];
}
}
vector<int> ans(3, 0);
int max_sum = 0;
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1], r = right[i + k];
int current_sum = prefix[l + k] - prefix[l] + prefix[i + k] - prefix[i] + prefix[r + k] - prefix[r];
if (current_sum > max_sum) {
max_sum = current_sum;
ans = {l, i, r};
}
}
return ans;
}
int main() {
vector<int> nums = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
vector<int> result = maxSumOfThreeSubarrays(nums, k);
for (int i : result) {
cout << i << " ";
}
return 0;
}function maxSumOfThreeSubarrays(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
const left = new Array(n).fill(0);
const right = new Array(n).fill(n - k);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (let i = k, total = prefix[k] - prefix[0]; i < n; i++) {
if (prefix[i + 1] - prefix[i + 1 - k] > total) {
total = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
left[i] = left[i - 1];
}
}
for (let i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
if (prefix[i + k] - prefix[i] >= total) {
total = prefix[i + k] - prefix[i];
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
let maxSum = 0;
const result = [0, 0, 0];
for (let i = k; i <= n - 2 * k; ++i) {
let l = left[i - 1];
let r = right[i + k];
let totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = l;
result[1] = i;
result[2] = r;
}
}
return result;
}
// Example usage
const nums = [1, 2, 1, 2, 6, 7, 5, 1];
const k = 2;
console.log(maxSumOfThreeSubarrays(nums, k));#include <stdio.h>
#include <stdlib.h>
void maxSumOfThreeSubarrays(int* nums, int numsSize, int k, int* returnSize) {
int prefix[numsSize + 1];
int left[numsSize];
int right[numsSize];
int result[3];
// Calculate the prefix sum array
prefix[0] = 0;
for (int i = 0; i < numsSize; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
// Calculate max left subarray positions
for (int i = k, total = prefix[k] - prefix[0]; i < numsSize; ++i) {
if (prefix[i + 1] - prefix[i + 1 - k] > total) {
total = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
left[i] = left[i - 1];
}
}
// Calculate max right subarray positions
right[numsSize - k] = numsSize - k;
for (int i = numsSize - k - 1, total = prefix[numsSize] - prefix[numsSize - k]; i >= 0; --i) {
if (prefix[i + k] - prefix[i] >= total) {
total = prefix[i + k] - prefix[i];
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
// Calculate max sum by considering middle subarray
int maxSum = 0;
for (int i = k; i <= numsSize - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = l;
result[1] = i;
result[2] = r;
}
}
*returnSize = 3;
for (int i = 0; i < 3; ++i) {
printf("%d ", result[i]);
}
}
int main() {
int nums[] = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
int returnSize;
maxSumOfThreeSubarrays(nums, 8, k, &returnSize);
return 0;
}using System;
public class Solution {
public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.Length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int[] left = new int[n];
int[] right = new int[n];
for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
if (prefix[i + 1] - prefix[i + 1 - k] > total) {
total = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
left[i] = left[i - 1];
}
}
for (int i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
if (prefix[i + k] - prefix[i] >= total) {
total = prefix[i + k] - prefix[i];
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
int[] ans = new int[3];
int maxSum = 0;
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int currentSum = prefix[i + k] - prefix[i] + prefix[l + k] - prefix[l] + prefix[r + k] - prefix[r];
if (currentSum > maxSum) {
maxSum = currentSum;
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}
return ans;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
int[] result = solution.MaxSumOfThreeSubarrays(nums, k);
Console.WriteLine(string.Join(", ", result));
}
}This Python solution computes prefix sums to simplify subarray calculations. It keeps track of the best possible subarray starting indices for the left and right subarrays. The middle subarray iterates to check for the highest achievable sum combining left, middle, and right subarrays. The process carefully maintains indices for lexicographical order.
Time Complexity: O(n), due to the iteration over the nums list for calculating prefix sums and subarray optimizations.
Space Complexity: O(n), required for storing prefix, left, and right arrays.
Approach 2: Dynamic Programming with Sliding Window
This approach employs dynamic programming alongside a sliding window to optimize subarray sum calculations and ensure non-overlapping conditions.
def maxSumOfThreeSubarraysDP(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + nums[i - 1]
left = [0] * n
right = [0] * n
dp = [0] * n
for i in range(k, n):
if prefix[i + 1] - prefix[i + 1 - k] > (dp[i - 1] if i - 1 >= 0 else 0):
dp[i] = prefix[i + 1] - prefix[i + 1 - k]
left[i] = i + 1 - k
else:
dp[i] = dp[i - 1]
left[i] = left[i - 1]
right[n - k] = n - k
for i in range(n - k - 1, -1, -1):
if prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]:
right[i] = i
else:
right[i] = right[i + 1]
max_sum = 0
result = [-1] * 3
for mid in range(k, n - 2 * k + 1):
l, r = left[mid - 1], right[mid + k]
total_sum = (prefix[l + k] - prefix[l]) + (prefix[mid + k] - prefix[mid]) + (prefix[r + k] - prefix[r])
if total_sum > max_sum:
max_sum = total_sum
result = [l, mid, r]
return result
# Example usage
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
print(maxSumOfThreeSubarraysDP(nums, k))import java.util.Arrays;
public class Main {
public static int[] maxSumOfThreeSubarraysDP(int[] nums, int k) {
int n = nums.length;
int[] prefix = new int[n + 1];
int[] dp = new int[n];
int[] left = new int[n];
int[] right = new int[n];
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (int i = k; i < n; ++i) {
if (prefix[i + 1] - prefix[i + 1 - k] > dp[i - 1]) {
dp[i] = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
dp[i] = dp[i - 1];
left[i] = left[i - 1];
}
}
right[n - k] = n - k;
for (int i = n - k - 1; i >= 0; --i) {
if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
int maxSum = 0;
int[] result = new int[3];
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result = new int[]{l, i, r};
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
int[] result = maxSumOfThreeSubarraysDP(nums, k);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> maxSumOfThreeSubarraysDP(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n, 0);
vector<int> prefix(n + 1, 0);
vector<int> left(n), right(n);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (int i = 0; i < k; ++i) {
dp[i] = prefix[i + 1];
}
for (int i = k; i < n; ++i) {
if (prefix[i + 1] - prefix[i + 1 - k] >= dp[i - 1]) {
dp[i] = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
dp[i] = dp[i - 1];
left[i] = left[i - 1];
}
}
right[n - k] = n - k;
for (int i = n - k - 1; i >= 0; --i) {
if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
vector<int> result(3);
int maxSum = 0;
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result = {l, i, r};
}
}
return result;
}
int main() {
vector<int> nums = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
vector<int> result = maxSumOfThreeSubarraysDP(nums, k);
for (int i : result) {
cout << i << " ";
}
return 0;
}function maxSumOfThreeSubarraysDP(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
const dp = new Array(n).fill(0);
const left = new Array(n).fill(0);
const right = new Array(n).fill(n - k);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (let i = k; i < n; i++) {
if (prefix[i + 1] - prefix[i + 1 - k] > dp[i - 1]) {
dp[i] = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
dp[i] = dp[i - 1];
left[i] = left[i - 1];
}
}
right[n - k] = n - k;
for (let i = n - k - 1; i >= 0; i--) {
if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
let maxSum = 0;
const result = [0, 0, 0];
for (let i = k; i <= n - 2 * k; ++i) {
let l = left[i - 1];
let r = right[i + k];
let totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = l;
result[1] = i;
result[2] = r;
}
}
return result;
}
// Example usage
const nums = [1, 2, 1, 2, 6, 7, 5, 1];
k = 2;
console.log(maxSumOfThreeSubarraysDP(nums, k));#include <stdio.h>
#include <stdlib.h>
void maxSumOfThreeSubarraysDP(int* nums, int numsSize, int k, int* returnSize) {
int* prefix = (int*)malloc((numsSize + 1) * sizeof(int));
int* left = (int*)malloc(numsSize * sizeof(int));
int* right = (int*)malloc(numsSize * sizeof(int));
int* dp = (int*)malloc(numsSize * sizeof(int));
int result[3] = {-1, -1, -1};
prefix[0] = 0;
for (int i = 0; i < numsSize; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (int i = 0; i < k; i++) {
dp[i] = prefix[i + 1];
}
for (int i = k; i < numsSize; ++i) {
if (prefix[i + 1] - prefix[i + 1 - k] >= dp[i - 1]) {
dp[i] = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
dp[i] = dp[i - 1];
left[i] = left[i - 1];
}
}
right[numsSize - k] = numsSize - k;
for (int i = numsSize - k - 1; i >= 0; --i) {
if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
int maxSum = 0;
for (int i = k; i <= numsSize - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = l;
result[1] = i;
result[2] = r;
}
}
*returnSize = 3;
for (int i = 0; i < 3; ++i) {
printf("%d ", result[i]);
}
free(prefix);
free(left);
free(right);
free(dp);
}
int main() {
int nums[] = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
int returnSize;
maxSumOfThreeSubarraysDP(nums, 8, k, &returnSize);
return 0;
}using System;
public class Solution {
public int[] MaxSumOfThreeSubarraysDP(int[] nums, int k) {
int n = nums.Length;
int[] prefix = new int[n + 1];
int[] dp = new int[n];
int[] left = new int[n];
int[] right = new int[n];
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
for (int i = k; i < n; ++i) {
if (prefix[i + 1] - prefix[i + 1 - k] > (dp[i - 1] if i - 1 >= 0 else 0)) {
dp[i] = prefix[i + 1] - prefix[i + 1 - k];
left[i] = i + 1 - k;
} else {
dp[i] = dp[i - 1];
left[i] = left[i - 1];
}
}
right[n - k] = n - k;
for (int i = n - k - 1; i >= 0; --i) {
if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
right[i] = i;
} else {
right[i] = right[i + 1];
}
}
int maxSum = 0;
int[] result = new int[3];
for (int i = k; i <= n - 2 * k; ++i) {
int l = left[i - 1];
int r = right[i + k];
int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = l;
result[1] = i;
result[2] = r;
}
}
return result;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
int k = 2;
int[] result = solution.MaxSumOfThreeSubarraysDP(nums, k);
Console.WriteLine(string.Join(", ", result));
}
}The Python solution employs dynamic programming principles with additional vectors to optimize calculation of subarray sums. The left and right arrays capture optimal prefix values dynamically during algorithm execution to achieve the best subarray combinations.
Time Complexity: O(n), as multiple linear passes determine subarray states.
Space Complexity: O(n), storing necessary data structures to reflect subarray calculations.
Approach 3: Sliding Window
We use a sliding window to enumerate the position of the third subarray, while maintaining the maximum sum and its position of the first two non-overlapping subarrays.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
const n: number = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const pre: number[][] = Array(n)
.fill([])
.map(() => new Array(2).fill(0));
const suf: number[][] = Array(n)
.fill([])
.map(() => new Array(2).fill(0));
for (let i = 0, t = 0, idx = 0; i < n - k + 1; ++i) {
const cur: number = s[i + k] - s[i];
if (cur > t) {
pre[i + k - 1] = [cur, i];
t = cur;
idx = i;
} else {
pre[i + k - 1] = [t, idx];
}
}
for (let i = n - k, t = 0, idx = 0; i >= 0; --i) {
const cur: number = s[i + k] - s[i];
if (cur >= t) {
suf[i] = [cur, i];
t = cur;
idx = i;
} else {
suf[i] = [t, idx];
}
}
let ans: number[] = [];
for (let i = k, t = 0; i < n - 2 * k + 1; ++i) {
const cur: number = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0];
if (cur > t) {
ans = [pre[i - 1][1], i, suf[i + k][1]];
t = cur;
}
}
return ans;
}func maxSumOfThreeSubarrays(nums []int, k int) []int {
ans := make([]int, 3)
s, s1, s2, s3 := 0, 0, 0, 0
mx1, mx12 := 0, 0
idx1, idx121, idx122 := 0, 0, 0
for i := k * 2; i < len(nums); i++ {
s1 += nums[i-k*2]
s2 += nums[i-k]
s3 += nums[i]
if i >= k*3-1 {
if s1 > mx1 {
mx1 = s1
idx1 = i - k*3 + 1
}
if mx1+s2 > mx12 {
mx12 = mx1 + s2
idx121 = idx1
idx122 = i - k*2 + 1
}
if mx12+s3 > s {
s = mx12 + s3
ans = []int{idx121, idx122, i - k + 1}
}
s1 -= nums[i-k*3+1]
s2 -= nums[i-k*2+1]
s3 -= nums[i-k+1]
}
}
return ans
}Approach 4: Preprocessing Prefix and Suffix + Enumerating Middle Subarray
We can preprocess to get the prefix sum array s of the array nums, where s[i] = sum_{j=0}^{i-1} nums[j]. Then for any i, j, s[j] - s[i] is the sum of the subarray [i, j).
Next, we use dynamic programming to maintain two arrays pre and suf of length n, where pre[i] represents the maximum sum and its starting position of the subarray of length k within the range [0, i], and suf[i] represents the maximum sum and its starting position of the subarray of length k within the range [i, n).
Then, we enumerate the starting position i of the middle subarray. The sum of the three subarrays is pre[i-1][0] + suf[i+k][0] + (s[i+k] - s[i]), where pre[i-1][0] represents the maximum sum of the subarray of length k within the range [0, i-1], suf[i+k][0] represents the maximum sum of the subarray of length k within the range [i+k, n), and (s[i+k] - s[i]) represents the sum of the subarray of length k within the range [i, i+k). We find the starting positions of the three subarrays corresponding to the maximum sum.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
func maxSumOfThreeSubarrays(nums []int, k int) (ans []int) {
n := len(nums)
s := make([]int, n+1)
for i := 0; i < n; i++ {
s[i+1] = s[i] + nums[i]
}
pre := make([][]int, n)
suf := make([][]int, n)
for i, t, idx := 0, 0, 0; i < n-k+1; i++ {
cur := s[i+k] - s[i]
if cur > t {
pre[i+k-1] = []int{cur, i}
t, idx = cur, i
} else {
pre[i+k-1] = []int{t, idx}
}
}
for i, t, idx := n-k, 0, 0; i >= 0; i-- {
cur := s[i+k] - s[i]
if cur >= t {
suf[i] = []int{cur, i}
t, idx = cur, i
} else {
suf[i] = []int{t, idx}
}
}
for i, t := k, 0; i < n-2*k+1; i++ {
cur := s[i+k] - s[i] + pre[i-1][0] + suf[i+k][0]
if cur > t {
ans = []int{pre[i-1][1], i, suf[i+k][1]}
t = cur
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum with Sliding Window | Time Complexity: O(n), due to the iteration over the nums list for calculating prefix sums and subarray optimizations. |
| Dynamic Programming with Sliding Window | Time Complexity: O(n), as multiple linear passes determine subarray states. |
| Sliding Window | – |
| Preprocessing Prefix and Suffix + Enumerating Middle Subarray | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with Sliding Window | O(n) | O(n) | Best general solution. Efficient for fixed 3-window problems and common in interviews. |
| Dynamic Programming with Sliding Window | O(n) | O(n) | Useful when extending the problem to select m non-overlapping subarrays. |
Frequently asked questions
Is Maximum Sum of 3 Non-Overlapping Subarrays easy or hard?
The problem is classified as Hard because it requires combining multiple techniques: sliding windows, prefix sums, and optimal substructure reasoning. The key challenge is realizing you can precompute the best left and right windows to reduce the search space to a linear scan.
Maximum Sum of 3 Non-Overlapping Subarrays Python/Java solution
Implementations typically compute window sums using a sliding window and then maintain best-left and best-right arrays. The same logic translates directly across Python, Java, C++, C#, and JavaScript because it relies only on array traversal and prefix calculations.
How to solve Maximum Sum of 3 Non-Overlapping Subarrays in O(n)?
First compute the sum of every k-length subarray using a sliding window. Build two arrays: one storing the best window from the left up to each index and another storing the best window from the right. Iterate through each possible middle window and combine it with the best left and right windows to maximize the total sum.
What is the best approach for Maximum Sum of 3 Non-Overlapping Subarrays?
The most efficient approach uses prefix sums with a sliding window and helper arrays to track the best left and right subarrays. It computes all k-length window sums and evaluates each possible middle window while referencing optimal windows on both sides. This produces the result in O(n) time with O(n) extra space.
Is Maximum Sum of 3 Non-Overlapping Subarrays asked at Google/Amazon/Meta?
This problem appears in interviews at large tech companies because it combines sliding window optimization with dynamic programming ideas. Variants of the problem have been reported in interviews at companies like Google, Amazon, and Meta where candidates must optimize subarray selection under constraints.
What data structure is used in Maximum Sum of 3 Non-Overlapping Subarrays?
The solution mainly uses arrays along with prefix sums and sliding window calculations. Helper arrays store the best subarray index seen so far from the left and from the right, enabling constant-time lookup when evaluating candidate combinations.
What is the time complexity of Maximum Sum of 3 Non-Overlapping Subarrays?
The optimal solution runs in O(n) time because each element is processed a constant number of times while building window sums and scanning for the best combination. Space complexity is O(n) due to prefix sums and helper arrays that store best left and right window indices.