两个非重叠子数组的最大和

标签: 数组 动态规划 滑动窗口

难度: Medium

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。

长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。

子数组是数组的一个 连续 部分。

示例 1：

输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。

示例 2：

输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

示例 3：

输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

提示：

  • 1 <= firstLen, secondLen <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Submission

运行时间: 32 ms

内存: 16.1 MB

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        return max(self.help(nums, firstLen, secondLen), self.help(nums, secondLen, firstLen))
    def help(self, nums, firstLen, secondLen):
        suml = sum(nums[:firstLen])
        maxSumL = suml
        sumr = 0
        for i in range(firstLen, firstLen + secondLen):
            sumr += nums[i]
        res = maxSumL + sumr
        j = firstLen
        for i in range(firstLen + secondLen, len(nums)):
            suml += nums[j] - nums[j-firstLen]
            maxSumL = max(maxSumL, suml)
            sumr += nums[i] - nums[i-secondLen]
            res = max(res, maxSumL + sumr)
            j += 1
        return res

Explain

该题解使用了滑动窗口的技术来找出两个指定长度的非重叠子数组的最大和。解决方案首先定义了一个辅助函数 `help`，该函数尝试确定一个长度为 `firstLen` 的子数组和一个长度为 `secondLen` 的子数组，这两个数组是不重叠的，并计算它们的和。函数首先计算出第一个长度为 `firstLen` 的子数组的和，并在数组中向后移动，同时维护一个长度为 `secondLen` 的第二个子数组。这两个子数组的起始位置是连续的。接下来，通过滑动窗口的方式更新这两个子数组的和，并记录下可能的最大和。最终，`maxSumTwoNoOverlap` 函数调用 `help` 函数两次，一次以 `firstLen, secondLen` 的顺序，另一次以 `secondLen, firstLen` 的顺序，返回这两次调用中的最大值，确保不论第一个还是第二个子数组哪个先开始都能找到最优解。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        # 从两种子数组长度的排列中选取最大值
        return max(self.help(nums, firstLen, secondLen), self.help(nums, secondLen, firstLen))
    def help(self, nums, firstLen, secondLen):
        # 初始化第一个长度为 firstLen 的子数组的和
        suml = sum(nums[:firstLen])
        maxSumL = suml
        # 初始化第二个长度为 secondLen 的子数组的和
        sumr = 0
        for i in range(firstLen, firstLen + secondLen):
            sumr += nums[i]
        # 计算当前两个子数组的总和
        res = maxSumL + sumr
        j = firstLen
        for i in range(firstLen + secondLen, len(nums)):
            # 更新第一个子数组的和
            suml += nums[j] - nums[j-firstLen]
            # 更新第一个子数组的最大和
            maxSumL = max(maxSumL, suml)
            # 更新第二个子数组的和
            sumr += nums[i] - nums[i-secondLen]
            # 更新最大的两个非重叠子数组的和
            res = max(res, maxSumL + sumr)
            j += 1
        return res

Explore

在`help`函数中，为了确保两个子数组不重叠，算法采用了严格的窗口移动策略。具体来说，首先使用固定长度`firstLen`初始化第一个子数组，然后立即初始化第二个子数组，其起始位置在第一个子数组结束的下一个位置，长度为`secondLen`。在滑动窗口更新过程中，对于第一个子数组，每次向右移动一个元素时，都会同时更新第二个子数组的起始位置，确保第二个子数组始终跟在第一个子数组后面开始，这样就维持了两个子数组的非重叠状态。

调用两次`help`函数是为了确保无论哪个子数组在前，都能找到最优解。由于两个子数组的长度`firstLen`和`secondLen`可能不同，其在数组中的位置和顺序可能影响到它们的总和。通过以`firstLen, secondLen`和`secondLen, firstLen`两种顺序分别计算，我们能比较两种情况下的最大和，从而确保不遗漏更优的组合，这样做可以全面地探索所有可能的非重叠子数组组合的最大和。

在更新`maxSumL`时，只考虑当前子数组的和是因为我们在寻找到目前为止的最大子数组和。`maxSumL`记录的是从数组开始到当前位置，所有可能的长度为`firstLen`的子数组中的最大和。这种方法确保了我们在考虑第二个子数组的位置和可能的和时，总是有一个准确且最大的第一个子数组和可用。虽然我们在每次迭代中只更新一次`maxSumL`，但由于它始终保持最大值，因此可以确保在任何时候计算两个子数组的总和时，总是基于最大可能的第一个子数组和来进行计算。