LC-1031 Medium LeetCode

1031. Maximum Sum of Two Non-Overlapping Subarrays

Array Dynamic Programming Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 60% Topics: Array, Dynamic Programming, Sliding Window

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def maxSumTwoNoOverlap(self, A, L, M):
        """
        :type A: List[int]
        :type L: int
        :type M: int
        :rtype: int
        """
        for i in xrange(1, len(A)):
            A[i] += A[i-1]
        result, L_max, M_max = A[L+M-1], A[L-1], A[M-1]
        for i in xrange(L+M, len(A)):
            L_max = max(L_max, A[i-M] - A[i-L-M])
            M_max = max(M_max, A[i-L] - A[i-L-M])
            result = max(result,
                         L_max + A[i] - A[i-M],
                         M_max + A[i] - A[i-L])
        return result

Solution from kamyu104/LeetCode-Solutions · MIT