1031. Maximum Sum of Two Non-Overlapping Subarrays

h1ros

Apr 22, 2019, 8:42:05 PM

Problem Setting¶

Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M. (For clarification, the L-length subarray could occur before or after the M-length subarray.)

Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:

0 <= i < i + L - 1 < j < j + M - 1 < A.length, or
0 <= j < j + M - 1 < i < i + L - 1 < A.length.

Example 1:¶

Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2

Output: 20

Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:¶

Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2

Output: 29

Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:¶

Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3

Output: 31

Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

Solution¶

This problem can be solved by dynamic programming approach where

Solution from lee215 ¶

This solution is $O(N)$ time and $O(1)$ space complexity.

In [18]:

class Solution(object):
    def maxSumTwoNoOverlap(self, A, L, M):
        for i in range(1, len(A)): # xrange -> range by Hiro
            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)): # xrange -> range by Hiro
            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] - A[i - M], Mmax + A[i] - A[i - L])
        return res

Execution¶

In [23]:

A = [0,6,5,2,2,5,1,9,4]; L = 1; M = 2
s = Solution()
s.maxSumTwoNoOverlap(A, L, M)

Out[23]:

Step-by-step¶

L3-4: the first loop creates cumulative sum of list A.

Highlight¶

This list of cumulative sum of elements are used to calculate the contiguous n elements by A[i - n] - A[i].

In [24]:

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

Out[24]:

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

In [25]:

for i in range(1, len(A)): # xrange -> range by Hiro
    A[i] += A[i - 1]
A

Out[25]:

[0, 6, 11, 13, 15, 20, 21, 30, 34]

L5:

res: initialize the variable for result
Lmax: Ls elements of the cumulative list i.e., 0 in the example 1
Mmax: M's elements of the cumulative list i.e., 6 in the example 1

In [27]:

res, Lmax, Mmax = A[L + M - 1], A[L - 1], A[M - 1]
res, Lmax, Mmax

Out[27]:

(11, 0, 6)

L6: the second loop starts from L+M to the end of the list.

Lmax is the case when L contiguous elements are taken first
Mmax is the case when M contiguous elements are taken first

Finally, it compares 2 cases (L elements first taken or M elements first taken) including the existing maximum result res.

In [35]:

res = A[L + M - 1]
for i in range(L + M, len(A)):
    print('='*40)
    print('processing at {}th element'.format(i))
    print('{} [{}] {}'.format(A[:i], A[i], A[i+1:]) )
    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] - A[i - M], Mmax + A[i] - A[i - L])

    print('Lmax:', Lmax)
    print('Mmax:', Mmax)
    print('A[i] - A[i - M]:', A[i] - A[i - M])
    print('A[i] - A[i - L]:', A[i] - A[i - L])
    
    print('Current maximum result:', res)

========================================
processing at 3th element
[0, 6, 11] [13] [15, 20, 21, 30, 34]
Lmax: 6
Mmax: 11
A[i] - A[i - M]: 7
A[i] - A[i - L]: 2
Current maximum result: 13
========================================
processing at 4th element
[0, 6, 11, 13] [15] [20, 21, 30, 34]
Lmax: 6
Mmax: 11
A[i] - A[i - M]: 4
A[i] - A[i - L]: 2
Current maximum result: 13
========================================
processing at 5th element
[0, 6, 11, 13, 15] [20] [21, 30, 34]
Lmax: 6
Mmax: 11
A[i] - A[i - M]: 7
A[i] - A[i - L]: 5
Current maximum result: 16
========================================
processing at 6th element
[0, 6, 11, 13, 15, 20] [21] [30, 34]
Lmax: 6
Mmax: 11
A[i] - A[i - M]: 6
A[i] - A[i - L]: 1
Current maximum result: 16
========================================
processing at 7th element
[0, 6, 11, 13, 15, 20, 21] [30] [34]
Lmax: 6
Mmax: 11
A[i] - A[i - M]: 10
A[i] - A[i - L]: 9
Current maximum result: 20
========================================
processing at 8th element
[0, 6, 11, 13, 15, 20, 21, 30] [34] []
Lmax: 6
Mmax: 11
A[i] - A[i - M]: 13
A[i] - A[i - L]: 4
Current maximum result: 20