Leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，先分别计算两个数组对应长度的连续子数组和，然后枚举所有符合条件的可能组合，找出最大和。Version 2使用前缀和，遍历前缀和，分别假设第一个子数组和在前和第二个子数组在前，求其最大值，即first和second，求第一个子数组的前缀和与当前的第二个子数组前缀和、第二个子数组的前缀和与当前的第一个子数组前缀和、之前最大和之间的最大值。为了便于计算以及索引校正，前缀和数组长度加1，初始值为0。

• Version 1

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        sum1 = 0
        sum2 = 0
        first = []
        second = []
        for i in range(n):
            if i < firstLen:
                sum1 += nums[i]
            else:
                first.append(sum1)
                sum1 = sum1 + nums[i] - nums[i - firstLen]
            if i < secondLen:
                sum2 += nums[i]
            else:
                second.append(sum2)
                sum2 = sum2 + nums[i] - nums[i - secondLen]
        first.append(sum1)
        second.append(sum2)
        maximum = 0
        for i in range(len(first)):
            for j in range(i + firstLen, len(second)):
                maximum = max(maximum, first[i] + second[j])
        for j in range(len(second)):
            for i in range(j + secondLen, len(first)):
                maximum = max(maximum, first[i] + second[j])
        return maximum

• Version 2

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        maximum = 0
        prefix = [0]
        for i in range(n):
            prefix.append(prefix[-1] + nums[i])
        first = 0
        second = 0
        for i in range(firstLen + secondLen, len(prefix)):
            first = max(first, prefix[i - secondLen] - prefix[i - firstLen - secondLen])
            second = max(second, prefix[i - firstLen] - prefix[i - firstLen - secondLen])
            maximum = max(maximum, prefix[i] - prefix[i - secondLen] + first, prefix[i] - prefix[i - firstLen] + second)
        return maximum

Reference

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