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.

Description Hints 1 Solution Video 21:18

1031. Maximum Sum of Two Non-Overlapping Subarrays

Medium61.4% acceptance1 company

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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

We can use prefix sums to calculate any subarray sum quickly. For each L length subarray, find the best possible M length subarray that occurs before and after it.

21:18

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[0,6,5,2,2,5,1,9,4]
1
2

Input

[3,8,1,3,2,1,8,9,0]
3
2

Input

[2,1,5,6,0,9,5,0,3,8]
4
3

Your code is saved on this device.Solution