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.
1using System;
2
3public class Solution {
4 public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
5 int n = nums.Length;
6 int[] prefix = new int[n + 1];
7 for (int i = 0; i < n; i++) {
8 prefix[i + 1] = prefix[i] + nums[i];
9 }
10 int[] left = new int[n];
11 int[] right = new int[n];
12 for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
13 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 C# solution combines prefix sums and sliding window principles to determine the maximum subarray sums for three non-overlapping sections within the input list. By maintaining correct indices for left and right subarrays, it efficiently finds the middle subarray to maximize the total 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#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;
}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.
The C++ implementation uses dynamic programming to store the cumulative sums and utilizes left and right arrays to preserve optimal positions for subarray ranges. This allows efficiently choosing and maintaining the best sums for the problem's conditions.