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)The key challenge in #689 Maximum Sum of 3 Non-Overlapping Subarrays is selecting three subarrays of fixed length k such that their total sum is maximized while ensuring they do not overlap. A common strategy combines prefix sums with dynamic programming and a sliding window technique.
First, compute the sum of every window of size k. This can be efficiently done using a sliding window so that each new window is updated in constant time. Next, maintain helper arrays that store the best window index from the left and the best window index from the right for every position. These arrays help quickly determine the optimal first and third subarrays when considering a middle subarray.
By iterating through possible middle subarray positions and combining them with the best choices on both sides, we can track the maximum total sum. This structured approach avoids brute force and ensures an efficient solution with linear time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window + Dynamic Programming | O(n) | O(n) |
NeetCodeIO
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.
Time Complexity: O(n), since we make a constant number of passes through the array.
Space Complexity: O(n), due to the prefix, left, and right arrays.
1import java.util.Arrays;
2
3public class Main {
4 public static int[] maxSumOfThreeSubarrays(int[] nums,
The Java solution uses a prefix sum array to quickly compute subarray sums. To identify the optimal subarrays, it employs two sliding window techniques (left and right) to track ideal starting indices for the leftmost and rightmost subarrays. The main loop determines the middle subarray and calculates the total possible sum.
This approach employs dynamic programming alongside a sliding window to optimize subarray sum calculations and ensure non-overlapping conditions.
Time Complexity: O(n), for traversal of the nums array multiple times.
Space Complexity: O(n), utilizing the dp, prefix, left, and right arrays.
1
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));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums or sliding windows allow efficient calculation of fixed-length subarray sums. Instead of recalculating sums repeatedly, each new window can be updated in constant time, reducing the overall complexity to linear time.
Yes, this type of problem is common in FAANG-style interviews because it tests dynamic programming, array manipulation, and optimization techniques. Candidates must combine multiple ideas like prefix sums and greedy selection efficiently.
Arrays are the primary data structures used in this problem. They store precomputed window sums and track the best left and right subarray indices, enabling constant-time lookups during iteration.
The optimal approach uses a combination of sliding window and dynamic programming. First compute sums of all subarrays of length k, then maintain best left and right choices for each position. This allows efficient evaluation of each possible middle subarray.
In C#, the code uses dynamic programming to manage cumulative sums, leveraging strategic indexing through left and right tracking arrays. This captures the strongest results with efficient stored sum calculations, thus finding optimal subarray triplets.