1031. Maximum Sum of Two Non-Overlapping Subarrays
Problem Description
Given an array nums
of integers and two distinct integer values firstLen
and secondLen
, the task is to find the maximum sum that can be achieved by taking two non-overlapping subarrays from nums
, with one subarray having a length of firstLen
and the other having a length of secondLen
. A subarray is defined as a sequence of elements from the array that are contiguous (i.e., no gaps in between). It is important to note that the subarray with length firstLen
can either come before or after the subarray with length secondLen
, but they cannot overlap.
Intuition
To solve this problem, an effective idea is to utilize the concept of prefix sums to quickly calculate the sum of elements in any subarray of the given nums
array. By using the prefix sums, you can determine the sum of elements in constant time, rather than recalculating it every time by adding up elements iteratively.
Here's the intuition broken down into steps:
-
Calculate prefix sums: First, we need to create an array of prefix sums
s
from the input arraynums
, which holds the sum of the elements from the start up to the current index. -
Initialize variables: We then define two variables
ans
to store the maximum sum found so far andt
to keep track of the maximum sum of subarrays of a particular length as we traverse the array. -
Find Maximum for each configuration:
- Start by considering subarrays of length
firstLen
and then move on to subarrays of lengthsecondLen
. As we iterate through the array, we calculate the maximum sum of afirstLen
subarray ending at the current index and store it int
. - Then we use this to calculate and update
ans
by adding the sum of the followingsecondLen
subarray. - We ensure that at each step, the chosen subarrays do not overlap by controlling the indices and lengths properly.
- Start by considering subarrays of length
-
Repeat the process in reverse: To ensure we are not missing out on any configuration (since the
firstLen
subarray can appear before or after thesecondLen
subarray), we reverse the lengths and repeat the procedure. -
Return the result: The maximum of all calculated sums is stored in
ans
, which we return as the final answer.
By iterating over each possible starting point for the firstLen
and secondLen
subarrays and efficiently calculating sums using the prefix array, we find the maximum sum of two non-overlapping subarrays of designated lengths.
Learn more about Dynamic Programming and Sliding Window patterns.
Solution Approach
The solution is built around the efficient use of a prefix sum array and two traversal patterns to evaluate all possible configurations of the two required subarrays.
Here are the steps involved in the implementation:
-
Prefix Sum Array: A prefix sum array
s
is constructed from the input arraynums
usinglist(accumulate(nums, initial=0))
. This function call essentially generates a new list where each element at indexi
represents the sum of thenums
array up to that index. -
Traverse and Compute for
firstLen
andsecondLen
: The algorithm starts off with two for loop constructs, each responsible for handling one of the two configurations:- The first for loop starts iterating after
firstLen
to leave room for the first subarray. Inside this loop,t
is calculated as the maximum sum of thefirstLen
subarray ending at the current index i. - It immediately computes the sum of the next
secondLen
subarray and updates the answerans
if needed, by adding the sum of the currentfirstLen
subarray (t
) and the sum of the consecutivesecondLen
subarray.
- The first for loop starts iterating after
-
Variable
t
andans
: The variablet
tracks the maximum sum of a subarray of lengthfirstLen
found up to the current position in the iteration (essentially, it holds the best answer found so far for the left side). The variableans
accumulates the maximum combined sum of two non-overlapping subarrays, comparing the sum of the current subarray offirstLen
plus the sum of the non-overlapping subarray ofsecondLen
. -
Repeat the Process for Reversed Lengths: After the first pass is completed, the same process is repeated, with the roles of
firstLen
andsecondLen
reversed. This ensures that all possible positions offirstLen
andsecondLen
subarrays are evaluated. -
Checking for Overlapping: While updating
ans
, care is taken to ensure that the subarrays do not overlap by controlling the sequence of index increments and subarray length considerations. -
Return the Maximum Sum: After both traversals, the variable
ans
holds the maximum sum possible without overlap, which is then returned.
By separately handling the cases for which subarray comes first, the function ensures it examines all possible configurations while efficiently computing sums using the prefix sum array, thus arriving at the correct maximum sum of two non-overlapping subarrays of given lengths.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Consider the array nums = [3, 5, 2, 1, 7, 3]
, with firstLen = 2
and secondLen = 3
.
Step 1: Prefix Sum Array
Construct a prefix sum array s
from nums
.
- Original
nums
array: [3, 5, 2, 1, 7, 3] - Prefix sum array
s
: [0, 3, 8, 10, 11, 18, 21]
The element at index i
in the prefix sum array represents the sum of all elements in nums
up to index i-1
.
Step 2: Traverse and Compute for firstLen, then secondLen
- Initialize
ans
to -infinity (or a very small number) andt
to 0. - Start the first for loop after
firstLen
(index is 2 in this case).
Step 3: Variable t and ans
- At index 2 (i = 2), we ignore because we cannot form both subarrays.
- At index 3 (i = 3),
t = max(t, s[3] - s[3 - firstLen])
which ismax(0, 10 - 3)
sot = 7
.
We then calculate the sum of the next secondLen
subarray: s[i + secondLen] - s[i]
which is s[6] - s[3]
so 18 - 10 = 8
. Since 8 (secondLen subarray sum) + 7 (firstLen subarray sum) = 15
is greater than ans
, we update ans
to 15.
Step 4: Repeat for Reversed Lengths
- We reset
t
to 0, and reverse thefirstLen
andsecondLen
. - Start the next for loop after
secondLen
(index is 3 in this case). - At index 3 (i = 3), we ignore because we cannot form both subarrays.
Checking for Overlapping
- At index 4 (i = 4),
t = max(t, s[4] - s[4 - secondLen])
which ismax(0, 11 - 3)
sot = 8
.
We then compute the sum of the next firstLen
subarray: s[i + firstLen] - s[i]
which is s[6] - s[4]
so 21 - 11 = 10
. We add 10 (firstLen subarray sum)
to 8 (secondLen subarray sum)
and get 10 + 8 = 18
which is greater than ans
, so we update ans
to 18.
Step 6: Return the Maximum Sum
We have finished evaluating both configurations. The variable ans
now holds the value 18
, which is the maximum sum of two non-overlapping subarrays for the lengths provided. Thus, we return 18
as the final answer for this example.
Solution Implementation
1from itertools import accumulate
2
3class Solution:
4 def max_sum_two_no_overlap(self, nums: List[int], first_len: int, second_len: int) -> int:
5 # Determine the total number of elements in nums
6 n = len(nums)
7
8 # Create a prefix sum array with an initial value of 0 for easier calculation
9 prefix_sums = list(accumulate(nums, initial=0))
10
11 # Initialize the answer and a temporary variable for tracking the max sum of the first array
12 max_sum = max_sum_first_array = 0
13
14 # Loop through nums to consider every possible second array starting from index first_len
15 i = first_len
16 while i + second_len - 1 < n:
17 # Find the max sum of the first array ending before the start of the second array
18 max_sum_first_array = max(max_sum_first_array, prefix_sums[i] - prefix_sums[i - first_len])
19 # Update the max_sum with the best we've seen combining the two arrays so far
20 max_sum = max(max_sum, max_sum_first_array + prefix_sums[i + second_len] - prefix_sums[i])
21 i += 1
22
23 # Reset the temporary variable for the max sum of first and second arrays
24 max_sum_second_array = 0
25 # Loop through nums to consider every possible first array starting from index second_len
26 i = second_len
27 while i + first_len - 1 < n:
28 # Find the max sum of the second array ending before the start of the first array
29 max_sum_second_array = max(max_sum_second_array, prefix_sums[i] - prefix_sums[i - second_len])
30 # Update the max_sum with the best we've seen for the swapped sizes of the two arrays
31 max_sum = max(max_sum, max_sum_second_array + prefix_sums[i + first_len] - prefix_sums[i])
32 i += 1
33
34 # Return the maximum sum found
35 return max_sum
36
1class Solution {
2 public int maxSumTwoNoOverlap(int[] numbers, int firstLength, int secondLength) {
3 // Initialize the length of the array
4 int arrayLength = numbers.length;
5 // Create a prefix sum array with an additional 0 at the beginning
6 int[] prefixSums = new int[arrayLength + 1];
7 // Calculate prefix sums
8 for (int i = 0; i < arrayLength; ++i) {
9 prefixSums[i + 1] = prefixSums[i] + numbers[i];
10 }
11
12 // Initialize the answer to be the maximum sum we are looking for
13 int maxSum = 0;
14
15 // First scenario: firstLength subarray is before secondLength subarray
16 // Loop from firstLength up to the point where a contiguous secondLength subarray can fit
17 for (int i = firstLength, tempMax = 0; i + secondLength - 1 < arrayLength; ++i) {
18 // Get the maximum sum of any firstLength subarray up to the current index
19 tempMax = Math.max(tempMax, prefixSums[i] - prefixSums[i - firstLength]);
20 // Update the maxSum with the sum of the maximum firstLength subarray and the contiguous secondLength subarray
21 maxSum = Math.max(maxSum, tempMax + prefixSums[i + secondLength] - prefixSums[i]);
22 }
23
24 // Second scenario: secondLength subarray is before firstLength subarray
25 // Loop from secondLength up to the point where a contiguous firstLength subarray can fit
26 for (int i = secondLength, tempMax = 0; i + firstLength - 1 < arrayLength; ++i) {
27 // Get the maximum sum of any secondLength subarray up to the current index
28 tempMax = Math.max(tempMax, prefixSums[i] - prefixSums[i - secondLength]);
29 // Update the maxSum with the sum of the maximum secondLength subarray and the contiguous firstLength subarray
30 maxSum = Math.max(maxSum, tempMax + prefixSums[i + firstLength] - prefixSums[i]);
31 }
32
33 // Return the maximum sum found for both scenarios
34 return maxSum;
35 }
36}
37
1#include <vector>
2#include <algorithm> // For std::max
3
4using std::vector;
5using std::max;
6
7class Solution {
8public:
9 int maxSumTwoNoOverlap(vector<int>& nums, int L, int M) {
10 int n = nums.size();
11 vector<int> prefixSum(n + 1, 0);
12 // Calculate prefix sums
13 for (int i = 0; i < n; ++i) {
14 prefixSum[i + 1] = prefixSum[i] + nums[i];
15 }
16
17 int maxSum = 0;
18 int maxL = 0; // To store max sum of subarray with length L
19
20 // Find max sum for two non-overlapping subarrays
21 // where first subarray has length L and second has length M
22 for (int i = L; i + M - 1 < n; ++i) {
23 maxL = max(maxL, prefixSum[i] - prefixSum[i - L]);
24 maxSum = max(maxSum, maxL + prefixSum[i + M] - prefixSum[i]);
25 }
26
27 int maxM = 0; // To store max sum of subarray with length M
28
29 // Same as above, but first subarray has length M and second has length L
30 for (int i = M; i + L - 1 < n; ++i) {
31 maxM = max(maxM, prefixSum[i] - prefixSum[i - M]);
32 maxSum = max(maxSum, maxM + prefixSum[i + L] - prefixSum[i]);
33 }
34
35 // Return the max possible sum of two non-overlapping subarrays
36 return maxSum;
37 }
38};
39
1// The `nums` array stores the integers, `L` and `M` are the lengths of the subarrays
2function maxSumTwoNoOverlap(nums: number[], L: number, M: number): number {
3 const n: number = nums.length;
4 const prefixSum: number[] = new Array(n + 1).fill(0);
5
6 // Calculate prefix sums
7 for (let i = 0; i < n; ++i) {
8 prefixSum[i + 1] = prefixSum[i] + nums[i];
9 }
10
11 let maxSum: number = 0; // Max sum of two non-overlapping subarrays
12 let maxL: number = 0; // Max sum of subarray with length L
13
14 // First loop: fixing the first subarray with length L and finding optimal M
15 for (let i = L; i + M <= n; ++i) {
16 maxL = Math.max(maxL, prefixSum[i] - prefixSum[i - L]);
17 maxSum = Math.max(maxSum, maxL + prefixSum[i + M] - prefixSum[i]);
18 }
19
20 let maxM: number = 0; // Max sum of subarray with length M
21
22 // Second loop: fixing the first subarray with length M and finding optimal L
23 for (let i = M; i + L <= n; ++i) {
24 maxM = Math.max(maxM, prefixSum[i] - prefixSum[i - M]);
25 maxSum = Math.max(maxSum, maxM + prefixSum[i + L] - prefixSum[i]);
26 }
27
28 // Return the max possible sum of two non-overlapping subarrays
29 return maxSum;
30}
31
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the length of the nums
list. This is because the code iterates over the list twice with while-loops. In each iteration, it performs a constant number of operations (addition, subtraction, and comparison).
The space complexity of the code is O(n)
, due to the additional list s
that is created with the accumulate
function to store the prefix sums of the nums
list. The size of the s
list is directly proportional to the size of the nums
list.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!