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.
1def maxSumOfThreeSubarrays(nums, k):
2 n = len(nums)
3 prefix = [0] * (n + 1)
4 for
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.
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
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 the Java solution, a dynamic programming array (dp) is utilized to track subarray sums. The code ensures efficient recalculations and coordinated updating of left and right best subarray indicators. The final middle subarray selection considers all these elements to find optimal results.