Problem statement

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

Solution

There is O(n^2) solution, which pass given constraints. However we can do better.

  1. First of all, there is two cases, when interval of length L is befor M and the opposite.
  2. Let us fix interval of length L. Then what choice we have for M if it is to the right of L?

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maxSumTwoNoOverlap(self, A, L, M):
        def maxSum(L, M):
            lft = [acc[i] - acc[i-L] for i in range(L, n + 1 - M)]
            lft = list(accumulate(lft, max))
            rgh = [acc[i+M] - acc[i] for i in range(L, n + 1 - M)]
            rgh = list(accumulate(rgh[::-1], max))[::-1]
            return max(x + y for x, y in zip(lft, rgh))

        acc = [0] + list(accumulate(A))
        n = len(A)
        return max(maxSum(L, M), maxSum(M, L))