Leetcode 1096 Solution

This article provides solution to leetcode question 1096 (maximum-sum-of-two-non-overlapping-subarrays)
Categories:
Tags:
Access this page by simply typing in "lcs 1096" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays

Solution

class Solution:
    def _maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)

        opt1 = [0] * n
        opt2 = [0] * n

        cur = sum(A[0:L])
        opt1[L - 1] = cur
        for i in range(L, n):
            cur += A[i] - A[i - L]
            opt1[i] = max(opt1[i - 1], cur)

        cur = sum(A[n - M:n])
        opt2[n - M] = cur
        for i in reversed(range(0, n - M)):
            cur += A[i] - A[i + M]
            opt2[i] = max(opt2[i + 1], cur)

        ans = 0
        for i in range(L - 1, n - M):
            ans = max(ans, opt1[i] + opt2[i + 1])
        return ans

    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        return max(
            self._maxSumTwoNoOverlap(A, L, M),
            self._maxSumTwoNoOverlap(A, M, L),
        )