Leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays

Problem Explanation

Given an array of non-negative integers A, the task is to find the maximum total sum when we choose two contiguous subarrays of lengths L and M. The subarrays must be non-overlapping which means that the numbers chosen in one subarray cannot be repeated in the second subarray.

For example, If A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2, one of the valid selections would be choosing the subarray [9] of length 1 and subarray [6,5] of length 2. The total sum of these subarrays = 9 + 6 + 5 = 20 which is the maximum total sum that can be obtained.

Solution Explanation

The problem can be solved with the help of dynamic programming. The approach is to build two arrays - one that stores the maximum sum for all possible L length subarrays until index i and the other that stores the maximum sum for all possible M length subarrays starting from index i. For this, we keep a rolling sum while traversing the array A and then exclude the (i-L+1)th element when we have processed L elements.

Next, we repeat the entire process again but the roles of L and M are now switched and we return the maximum between the previous result and the current result.

Let's walk through an example: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3

From the left, we build the maximum L length subarrays which results in,

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

left = [0,0,0,13,13,14,19,19,19,19]```

and from the right,

1
2right = [23,23,23,20,20,18,16,11,8,0]```
3
4
5
6Notice that the `right` array is shifted by one index.
7
8Finally, we calculate the maximum from `left[i] + right[i+1]` which gives us the maximum sum of `31`.
9
10### Python Solution 

python class Solution: def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int: def helper(A, l, m): for i in range(1, len(A)): A[i] += A[i-1] res, lmax, mmax = A[l+m-1], A[l-1], A[m-1] for i in range(l+m, len(A)): lmax = max(lmax, A[i-m] - A[i-l-m]) mmax = max(mmax, A[i-l] - A[i-l-m]) res = max(res, lmax + A[i-m] - A[i-l-m], mmax + A[i-l] - A[i-l-m]) return res return max(helper(A[:], L, M), helper(A[:], M, L))

1
2
3
4### Java Solution

java class Solution { public int maxSumTwoNoOverlap(int[] A, int L, int M) { for (int i = 1; i < A.length; ++i) A[i] += A[i - 1]; int res = A[L + M - 1], Lmax = A[L - 1], Mmax = A[M - 1]; for (int i = L + M; i < A.length; ++i) { Lmax = Math.max(Lmax, A[i - M] - A[i - L - M]); Mmax = Math.max(Mmax, A[i - L] - A[i - L - M]); res = Math.max(res, Math.max(Lmax + A[i] - A[i - M], Mmax + A[i - L] - A[i - L - M])); } return res; } }

1
2
3
4### JavaScript Solution

javascript var maxSumTwoNoOverlap = function(A, L, M) { for(let i=1;i<A.length;i++){ A[i]+=A[i-1]; } let res=A[L+M-1], Lmax=A[L-1], Mmax=A[M-1]; for(let i=L+M;i<A.length;i++){ Lmax=Math.max(Lmax,A[i-M]-A[i-L-M]); Mmax=Math.max(Mmax,A[i-L]-A[i-L-M]); res=Math.max(res,Math.max(Lmax+A[i]-A[i-M],Mmax+A[i-L]-A[i-L-M])); } return res; };

1
2Overall, the solutions in Python, Java, and JavaScript use the same fundamental approach to solve the problem. They compute prefix sums for the array, then they iterate through the array to figure out the maximum sums of two non-overlapping subarrays. The solutions first initialize the variables `res`, `Lmax`, and `Mmax`, where `res` is the maximum total sum, `Lmax` is the maximum sum we can get from a subarray of length `L` and `Mmax` is the maximum sum we can get from a subarray of length `M`. Starting from index `L+M`, we then move through the array to update `res`, `Lmax`, and `Mmax`.
3
4A few crucial points in this process are:
5
6- We use `A[i - M] - A[i - L - M]` to get the sum of the subarray of length `L` ending exactly before a length M interval ends at i. Similarly, `A[i - L] - A[i - L - M]` is used to get the sum of the subarray of length `M` ending exactly before a length L interval ends at i.
7
8- In each iteration `i`, `Lmax` gets updated to the maximum value between its current value and the sum of the subarray of length `L` ending exactly where the length `M` interval starts before `i`, and `Mmax` gets updated to the maximum value between its current value and the sum of the subarray of length `M` ending exactly where the length `L` interval starts at `i`.
9
10- The variable `res` is always updated to be the maximum value among its current value, the sum adding `Lmax` and the sum of length `M` interval ending at `i`, and the sum adding `Mmax` and the sum of length `L` interval ending at `i`.
11
12- By performing the helper function twice with `L` and `M` swapped, we ensure that we account for all possible configurations of `L` and `M` length intervals.
13
14The time complexity of this approach is `O(n)`, where `n` is the length of the array `A`, as each element is visited only once. And the space complexity is also `O(n)` since we're modifying the input array to store the prefix sums.