Skip to main content
Talentd

Maximum Sum of 3 Non-Overlapping Subarrays - Solution & Explanation

HardArrayDynamic Programming30 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 * 104
  • 1 <= nums[i] < 216
  • 1 <= k <= floor(nums.length / 3)

Approach Overview

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 1: Prefix Sum with Sliding Window

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.

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[].

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming with Sliding Window

This approach employs dynamic programming alongside a sliding window to optimize subarray sum calculations and ensure non-overlapping conditions.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), for traversal of the nums array multiple times.
Space Complexity: O(n), utilizing the dp, prefix, left, and right arrays.

Try this approach in the editor →

Approach 3: Sliding Window

We use a sliding window to enumerate the position of the third subarray, while maintaining the maximum sum and its position of the first two non-overlapping subarrays.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Preprocessing Prefix and Suffix + Enumerating Middle Subarray

We can preprocess to get the prefix sum array s of the array nums, where s[i] = sum_{j=0}^{i-1} nums[j]. Then for any i, j, s[j] - s[i] is the sum of the subarray [i, j).

Next, we use dynamic programming to maintain two arrays pre and suf of length n, where pre[i] represents the maximum sum and its starting position of the subarray of length k within the range [0, i], and suf[i] represents the maximum sum and its starting position of the subarray of length k within the range [i, n).

Then, we enumerate the starting position i of the middle subarray. The sum of the three subarrays is pre[i-1][0] + suf[i+k][0] + (s[i+k] - s[i]), where pre[i-1][0] represents the maximum sum of the subarray of length k within the range [0, i-1], suf[i+k][0] represents the maximum sum of the subarray of length k within the range [i+k, n), and (s[i+k] - s[i]) represents the sum of the subarray of length k within the range [i, i+k). We find the starting positions of the three subarrays corresponding to the maximum sum.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum with Sliding Window

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.

Dynamic Programming with Sliding Window

Time Complexity: O(n), for traversal of the nums array multiple times.
Space Complexity: O(n), utilizing the dp, prefix, left, and right arrays.

Sliding Window—
Preprocessing Prefix and Suffix + Enumerating Middle Subarray—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum with Sliding WindowO(n)O(n)Best general solution. Efficient for fixed 3-window problems and common in interviews.
Dynamic Programming with Sliding WindowO(n)O(n)Useful when extending the problem to select m non-overlapping subarrays.

Video Solution

Maximum Sum of 3 Non-Overlapping Subarrays - Leetcode 689 - Python • NeetCodeIO • 13,868 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Sum of 3 Non-Overlapping Subarrays easy or hard?
The problem is classified as Hard because it requires combining multiple techniques: sliding windows, prefix sums, and optimal substructure reasoning. The key challenge is realizing you can precompute the best left and right windows to reduce the search space to a linear scan.
Maximum Sum of 3 Non-Overlapping Subarrays Python/Java solution
Implementations typically compute window sums using a sliding window and then maintain best-left and best-right arrays. The same logic translates directly across Python, Java, C++, C#, and JavaScript because it relies only on array traversal and prefix calculations.
How to solve Maximum Sum of 3 Non-Overlapping Subarrays in O(n)?
First compute the sum of every k-length subarray using a sliding window. Build two arrays: one storing the best window from the left up to each index and another storing the best window from the right. Iterate through each possible middle window and combine it with the best left and right windows to maximize the total sum.
What is the best approach for Maximum Sum of 3 Non-Overlapping Subarrays?
The most efficient approach uses prefix sums with a sliding window and helper arrays to track the best left and right subarrays. It computes all k-length window sums and evaluates each possible middle window while referencing optimal windows on both sides. This produces the result in O(n) time with O(n) extra space.
Is Maximum Sum of 3 Non-Overlapping Subarrays asked at Google/Amazon/Meta?
This problem appears in interviews at large tech companies because it combines sliding window optimization with dynamic programming ideas. Variants of the problem have been reported in interviews at companies like Google, Amazon, and Meta where candidates must optimize subarray selection under constraints.
What data structure is used in Maximum Sum of 3 Non-Overlapping Subarrays?
The solution mainly uses arrays along with prefix sums and sliding window calculations. Helper arrays store the best subarray index seen so far from the left and from the right, enabling constant-time lookup when evaluating candidate combinations.
What is the time complexity of Maximum Sum of 3 Non-Overlapping Subarrays?
The optimal solution runs in O(n) time because each element is processed a constant number of times while building window sums and scanning for the best combination. Space complexity is O(n) due to prefix sums and helper arrays that store best left and right window indices.

Ready to solve this problem?

Practice Maximum Sum of 3 Non-Overlapping Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Best Time to Buy and Sell Stock III

Next

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values