Watch 10 video solutions for Maximum Sum of 3 Non-Overlapping Subarrays, a hard level problem involving Array, Dynamic Programming. This walkthrough by NeetCodeIO has 13,363 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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)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 | 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. |