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.
1#include <stdio.h>
2#include <stdlib.h>
3
4void maxSumOfThreeSubarrays(int* nums, int numsSize, int k, int* returnSize)
This C solution uses three arrays:
prefix[] for prefix sums to compute subarray sums quickly.left[] to store the starting index of the max subarray sum from the left.right[] to store the starting index of the max subarray sum from the right.It iterates over potential middle subarray starting points and uses these auxiliary arrays to compute the total sum efficiently. Updates are made to get the largest sum and store associated index positions in result[].
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.
This C solution introduces a dynamic programming table (dp) to record the maximum sum up to each point. Using left and right tracking, it determines the best left and right subarrays. A single pass checks for optimal middle subarrays using this dynamic information.