BinarySearch 0602 Max Sum of Two Non-Overlapping Lists

Problem statement

https://binarysearch.com/problems/Max-Sum-of-Two-Non-Overlapping-Lists/

Solution

Equal to Leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays

Complexity

Code

class Solution:
    def solve(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))