1031.md

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution 1 (time O(n), space O(n))

class Solution(object):
    def maxSumTwoNoOverlap(self, nums, firstLen, secondLen):
        """
        :type nums: List[int]
        :type firstLen: int
        :type secondLen: int
        :rtype: int
        """
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        self.ans = 0

        def solve(firstLen, secondLen):
            max_sum_1 = 0
            for i in range(firstLen + secondLen, n + 1):
                max_sum_1 = max(max_sum_1, prefix_sum[i - secondLen] - prefix_sum[i - secondLen - firstLen])
                self.ans = max(self.ans, max_sum_1 + prefix_sum[i] - prefix_sum[i - secondLen])

        solve(firstLen, secondLen)
        solve(secondLen, firstLen)
        return self.ans