1031. Maximum Sum of Two Non-Overlapping Subarrays

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

solution

• 注意利用已知条件: 有且只有两个

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        def get_maxsum(l, r):
            max_l = ans = 0
            for i in range(l+r, len(prefix)):
                max_l = max(max_l, prefix[i-r] - prefix[i-r-l])
                ans = max(ans, max_l + prefix[i] - prefix[i-r])
            return ans
        
        prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            prefix[i+1] = prefix[i] + num
        return max(get_maxsum(firstLen, secondLen), get_maxsum(secondLen, firstLen))        

时间复杂度：O() 空间复杂度：O()