Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Sum of Two Non-Overlapping Subarrays solution and explanation

MediumArrayDynamic ProgrammingSliding Window6 min read61.4% acceptanceUpdated 9 Apr 2026
Asked atAmazon
Practise Maximum Sum of Two Non-Overlapping Subarrays
21:18
Maximum Sum Of Two Non Overlapping Subarrays | Dynamic Programming-1-1-0Pepcoding · 21:18 · 21K viewsWatch on YouTube
9 more videos on this problem
  1. Maximum Sum Of Two Non Overlapping Subarrays | Dynamic Programming-1-1-0Pepcoding · 21:18 · 21K views
  2. maximum-sum-of-two-non-overlapping-subarrays || LeetcodePepcoding · 15:37 · 7K views
  3. 1031. Maximum Sum Of Two Non-Overlapping Subarrays (Leetcode Medium)Programming Live with Larry · 32:11 · 5K views
  4. LeetCode 1031. Maximum Sum of Two Non-Overlapping Subarrays | JSer - JavaScript & AlgorithmJSer · 26:19 · 4K views
  5. Leetcode : 1031 - Maximum Sum of Two Non-Overlapping SubarraysVarun Kumar · 8:26 · 1K views
  6. Maximum Sum of Two Non-Overlapping Subarrays | leetcode-1031| Dart | c++LinuxMan · 15:20 · 1K views
  7. leetcode 1031 Maximum Sum of Two Non Overlapping Subarrays (prefix sum)LetsCode · 9:16 · 641 views
  8. Maximum Sum Of Two Non-Overlapping SubarraysOwen Wu · 8:54 · 143 views
  9. Maximum Sum of Two Non-Overlapping Subarrays, Medium, LeetCode 1031H William Polenz · 1:01:13 · 70 views
  10. LeetCode Medium: 1031. Maximum Sum of Two Non Overlapping Subarraysrobzingcod · 23:16 · 44 views

The problem

Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen.

The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [0,3,8] with length 3.

Constraints:

  • 1 <= firstLen, secondLen <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Approach overview

Problem Overview: You are given an integer array and two lengths L and M. The task is to find two non-overlapping subarrays of these lengths whose combined sum is maximum. The order can be either L before M or M before L, but the subarrays must not overlap.

Approach 1: Prefix Sum and Sliding Window Technique (O(n) time, O(n) space)

This approach combines array prefix sums with a sliding window scan. First compute a prefix sum array so any subarray sum can be retrieved in O(1). Then iterate through the array while tracking the best possible subarray of length L seen so far before a window of length M. For each position, calculate the sum of the current M-length window and add it to the maximum L-length window found earlier. Repeat the process with the order reversed (M before L) because the larger result might come from either arrangement.

The key insight is that you never need to recompute previous windows. Instead, maintain a running maximum for the earlier window and update the answer while sliding the later window forward. This produces a linear scan of the array and avoids nested loops. Time complexity is O(n) and extra space is O(n) for the prefix sums (or O(1) if window sums are maintained incrementally).

Approach 2: Dynamic Programming Approach (O(n) time, O(n) space)

This approach uses dynamic programming to precompute the best subarray sums from both directions. Build two helper arrays: leftMax[i] stores the maximum sum of an L-length subarray ending at or before index i, and rightMax[i] stores the maximum sum of an M-length subarray starting at or after index i. These arrays allow you to combine non-overlapping segments efficiently.

After filling these arrays, iterate across the split point between the two subarrays. For every index, combine the best left segment with the best right segment. Run the same process again with L and M swapped to cover both possible orders. The DP arrays remove the need for recomputation and keep the algorithm linear.

This method is slightly more explicit than the sliding window technique because it stores intermediate results. It is useful when you want a clear separation between prefix computations and the final aggregation step.

Recommended for interviews: The prefix sum + sliding window solution is what most interviewers expect. It shows that you recognize the sliding window pattern and can optimize subarray calculations to O(n). Explaining the brute-force idea (checking all pairs of subarrays in O(n^2)) demonstrates understanding, but implementing the linear-time window technique shows strong problem-solving skills.

Approach 1: Prefix Sum and Sliding Window Technique

This approach uses prefix sums to calculate the sums of possible subarrays efficiently and then utilizes the sliding window technique to maintain maximum sums of the first and second subarrays non-overlappingly.

def maxSumTwoNoOverlap(nums, firstLen, secondLen):
    n = len(nums)
    prefixSum = [0] * (n + 1)
    for i in range(n):
        prefixSum[i + 1] = prefixSum[i] + nums[i]

    def calculateMax(len1, len2):
        maxFirst, result = 0, 0
        for i in range(len1, n - len2 + 1):
            maxFirst = max(maxFirst, prefixSum[i] - prefixSum[i - len1])
            result = max(result, maxFirst + prefixSum[i + len2] - prefixSum[i])
        return result

    return max(calculateMax(firstLen, secondLen), calculateMax(secondLen, firstLen))
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        return Math.max(
                calculateMax(prefixSum, firstLen, secondLen, n),
                calculateMax(prefixSum, secondLen, firstLen, n)
        );
    }

    private int calculateMax(int[] prefixSum, int len1, int len2, int n) {
        int maxFirst = 0, result = 0;
        for (int i = len1; i <= n - len2; i++) {
            maxFirst = Math.max(maxFirst, prefixSum[i] - prefixSum[i - len1]);
            result = Math.max(result, maxFirst + prefixSum[i + len2] - prefixSum[i]);
        }
        return result;
    }
}
#include <vector>
#include <algorithm>
using namespace std;

int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
    int n = nums.size();
    vector<int> prefixSum(n+1, 0);
    for (int i = 0; i < n; ++i) {
        prefixSum[i+1] = prefixSum[i] + nums[i];
    }

    int maxFirst = 0, maxSecond = 0, result = 0;
    for (int i = firstLen; i <= n - secondLen; ++i) {
        maxFirst = max(maxFirst, prefixSum[i] - prefixSum[i - firstLen]);
        result = max(result, maxFirst + prefixSum[i + secondLen] - prefixSum[i]);
    }
    for (int i = secondLen; i <= n - firstLen; ++i) {
        maxSecond = max(maxSecond, prefixSum[i] - prefixSum[i - secondLen]);
        result = max(result, maxSecond + prefixSum[i + firstLen] - prefixSum[i]);
    }

    return result;
}
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    const n = nums.length;
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    const calculateMax = (len1, len2) => {
        let maxFirst = 0, result = 0;
        for (let i = len1; i <= n - len2; i++) {
            maxFirst = Math.max(maxFirst, prefixSum[i] - prefixSum[i - len1]);
            result = Math.max(result, maxFirst + prefixSum[i + len2] - prefixSum[i]);
        }
        return result;
    };

    return Math.max(calculateMax(firstLen, secondLen), calculateMax(secondLen, firstLen));
};
#include <stdio.h>
#include <stdlib.h>

int maxSumTwoNoOverlap(int* nums, int numsSize, int firstLen, int secondLen) {
    int *prefixSum = (int *)malloc((numsSize + 1) * sizeof(int));
    prefixSum[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    int maxFirst = prefixSum[firstLen], maxSecond = prefixSum[secondLen];
    int result = prefixSum[firstLen + secondLen];

    for (int i = firstLen + secondLen; i <= numsSize; i++) {
        maxFirst = fmax(maxFirst, prefixSum[i - secondLen] - prefixSum[i - secondLen - firstLen]);
        result = fmax(result, maxFirst + prefixSum[i] - prefixSum[i - secondLen]);
    }

    for (int i = firstLen + secondLen; i <= numsSize; i++) {
        maxSecond = fmax(maxSecond, prefixSum[i - firstLen] - prefixSum[i - firstLen - secondLen]);
        result = fmax(result, maxSecond + prefixSum[i] - prefixSum[i - firstLen]);
    }

    free(prefixSum);
    return result;
}
public class Solution {
    public int MaxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.Length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        return Math.Max(
            CalculateMax(prefixSum, firstLen, secondLen, n),
            CalculateMax(prefixSum, secondLen, firstLen, n));
    }

    private int CalculateMax(int[] prefixSum, int len1, int len2, int n) {
        int maxFirst = 0, result = 0;
        for (int i = len1; i <= n - len2; i++) {
            maxFirst = Math.Max(maxFirst, prefixSum[i] - prefixSum[i - len1]);
            result = Math.Max(result, maxFirst + prefixSum[i + len2] - prefixSum[i]);
        }
        return result;
    }
}

The solution uses prefix sums to efficiently manage subarray sums and applies a helper function to evaluate max sums for different subarray sequences leveraging an efficient sliding window implementation.

Complexity

Time Complexity: O(n). Space Complexity: O(n), derived from prefix sums.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

This approach uses dynamic programming to keep track of maximum sums of subarrays of specific lengths at each position in the array. This strategy allows for efficient computation of non-overlapping subarray sums by leveraging previous maximum computations.

def maxSumTwoNoOverlap(nums, L, M):
    lMax = mMax = result = 0
    lSum = mSum = 0
    for i in range(L + M, len(nums) + 1):
        lSum += nums[i - 1]
        mSum += nums[i - 1]
        if i > L + M:
            lSum -= nums[i - L - 1]
            mSum -= nums[i - M - 1]
        if i >= M:
            mMax = max(mMax, mSum - nums[i - M])
        if i >= L:
            lMax = max(lMax, lSum - nums[i - L])

        if i >= L + M:
            mFirst = mMax + lSum
            lFirst = lMax + mSum
            result = max(result, mFirst, lFirst)

    return result
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int L, int M) {
        int lMax = 0, mMax = 0, result = 0;
        for (int i = L + M, lSum = 0, mSum = 0; i <= nums.length; ++i) {
            lSum += nums[i - 1];
            mSum += nums[i - 1];
            if (i > L + M) {
                lSum -= nums[i - L - 1];
                mSum -= nums[i - M - 1];
            }
            if (i >= M) mMax = Math.max(mMax, mSum - nums[i - M]);
            if (i >= L) lMax = Math.max(lMax, lSum - nums[i - L]);

            if (i >= L + M) {
                int mFirst = mMax + lSum;
                int lFirst = lMax + mSum;
                result = Math.max(result, Math.max(mFirst, lFirst));
            }
        }
        return result;
    }
}
#include <vector>
#include <algorithm>
using namespace std;

int maxSumTwoNoOverlap(vector<int>& nums, int L, int M) {
    int lMax = 0, mMax = 0, result = 0;
    for (int i = L + M, lSum = 0, mSum = 0; i <= nums.size(); ++i) {
        lSum += nums[i - 1];
        mSum += nums[i - 1];
        if (i > L + M) {
            lSum -= nums[i - L - 1];
            mSum -= nums[i - M - 1];
        }
        if (i >= M) mMax = max(mMax, mSum - nums[i - M]);
        if (i >= L) lMax = max(lMax, lSum - nums[i - L]);

        if (i >= L + M) {
            int mFirst = mMax + lSum;
            int lFirst = lMax + mSum;
            result = max({result, mFirst, lFirst});
        }
    }
    return result;
}
var maxSumTwoNoOverlap = function(nums, L, M) {
    let lMax = 0, mMax = 0, result = 0;
    let lSum = 0, mSum = 0;
    const n = nums.length;
    for (let i = L + M; i <= n; ++i) {
        lSum += nums[i - 1];
        mSum += nums[i - 1];
        if (i > L + M) {
            lSum -= nums[i - L - 1];
            mSum -= nums[i - M - 1];
        }
        if (i >= M) mMax = Math.max(mMax, mSum - nums[i - M]);
        if (i >= L) lMax = Math.max(lMax, lSum - nums[i - L]);

        if (i >= L + M) {
            const mFirst = mMax + lSum;
            const lFirst = lMax + mSum;
            result = Math.max(result, mFirst, lFirst);
        }
    }
    return result;
};
#include <stdio.h>

int maxSumTwoNoOverlap(int* nums, int numsSize, int L, int M) {
    int lMax = 0, mMax = 0, result = 0;
    for (int i = L + M, lSum = 0, mSum = 0; i <= numsSize; ++i) {
        lSum += nums[i - 1];
        mSum += nums[i - 1];
        if (i > L + M) {
            lSum -= nums[i - L - 1];
            mSum -= nums[i - M - 1];
        }
        if (i >= M) mMax = mMax > mSum - nums[i - M] ? mMax : mSum - nums[i - M];
        if (i >= L) lMax = lMax > lSum - nums[i - L] ? lMax : lSum - nums[i - L];

        if (i >= L + M) {
            int mFirst = mMax + lSum;
            int lFirst = lMax + mSum;
            result = result > mFirst ? result : mFirst;
            result = result > lFirst ? result : lFirst;
        }
    }
    return result;
}
public class Solution {
    public int MaxSumTwoNoOverlap(int[] nums, int L, int M) {
        int lMax = 0, mMax = 0, result = 0;
        int lSum = 0, mSum = 0;
        for (int i = L + M; i <= nums.Length; ++i) {
            lSum += nums[i - 1];
            mSum += nums[i - 1];
            if (i > L + M) {
                lSum -= nums[i - L - 1];
                mSum -= nums[i - M - 1];
            }
            if (i >= M) mMax = Math.Max(mMax, mSum - nums[i - M]);
            if (i >= L) lMax = Math.Max(lMax, lSum - nums[i - L]);

            if (i >= L + M) {
                int mFirst = mMax + lSum;
                int lFirst = lMax + mSum;
                result = Math.Max(result, Math.Max(mFirst, lFirst));
            }
        }

        return result;
    }
}

By managing rolling states using dynamic programming, the solution quickly updates maximum values of L-length and M-length subarrays. Through this method, the overall computation is achieved in linear time with reduced space requirements.

Complexity

Time Complexity: O(n), as a single traversal is needed. Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) (ans int) {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	for i, t := firstLen, 0; i+secondLen-1 < n; i++ {
		t = max(t, s[i]-s[i-firstLen])
		ans = max(ans, t+s[i+secondLen]-s[i])
	}
	for i, t := secondLen, 0; i+firstLen-1 < n; i++ {
		t = max(t, s[i]-s[i-secondLen])
		ans = max(ans, t+s[i+firstLen]-s[i])
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Prefix Sum and Sliding Window Technique

Time Complexity: O(n). Space Complexity: O(n), derived from prefix sums.

Dynamic Programming Approach

Time Complexity: O(n), as a single traversal is needed. Space Complexity: O(1).

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force (check all subarray pairs)O(n^2)O(1)Conceptual baseline or very small arrays
Prefix Sum + Sliding WindowO(n)O(n) or O(1)Best general solution and commonly expected in interviews
Dynamic Programming with Left/Right Max ArraysO(n)O(n)When you want explicit precomputed maximum segments from both directions

Frequently asked questions

Is Maximum Sum of Two Non-Overlapping Subarrays easy or hard?

The problem is rated Medium because it requires combining two techniques: sliding window and prefix sums. Once the idea of tracking the best previous window is recognized, the implementation becomes a straightforward linear scan.

Maximum Sum of Two Non-Overlapping Subarrays Python/Java solution

Python and Java implementations typically compute prefix sums, then iterate while maintaining the best previous window of length L or M. Each step updates the maximum combined sum in O(1), producing an overall O(n) solution.

How to solve Maximum Sum of Two Non-Overlapping Subarrays in O(n)?

First compute prefix sums so any subarray sum can be calculated in constant time. While iterating through the array, keep track of the maximum L-length window seen before the current M-length window and update the result. Repeat the process with the order reversed to handle both L-before-M and M-before-L cases.

What is the best approach for Maximum Sum of Two Non-Overlapping Subarrays?

The most efficient approach uses prefix sums with a sliding window. Track the best subarray of one length seen so far and combine it with the current window of the other length while scanning the array. This guarantees non-overlapping segments and runs in O(n) time with O(n) or O(1) space.

Is Maximum Sum of Two Non-Overlapping Subarrays asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving sliding windows and prefix sums. Variants of the problem have appeared in interviews at companies like Google, Amazon, and Meta where candidates are expected to derive the O(n) window-based solution.

What data structure is used in Maximum Sum of Two Non-Overlapping Subarrays?

The core structure is an array with prefix sums to compute subarray totals quickly. The algorithm also uses sliding window pointers and sometimes dynamic programming arrays to store the best subarray sums encountered so far.

What is the time complexity of Maximum Sum of Two Non-Overlapping Subarrays?

The optimal solution runs in O(n) time because the array is scanned a constant number of times while maintaining sliding windows and prefix sums. Space complexity is O(n) if a prefix array is used, or O(1) if window sums are maintained directly.

Comments

Now write it yourselfClose this page and solve Maximum Sum of Two Non-Overlapping Subarrays in the editor, without looking.
Practise Maximum Sum of Two Non-Overlapping Subarrays