Question

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

English Version

题目描述

给你一个整数数组 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

解法

方法一：前缀和 + 枚举

我们先预处理得到数组 nums 的前缀和数组 $s$，其中 $s[i]$ 表示 $nums$ 中前 $i$ 个元素的和。

接下来，我们分两种情况枚举：

假设 $firstLen$ 个元素的子数组在 $secondLen$ 个元素的子数组的左边，那么我们可以枚举 $secondLen$ 个元素的子数组的左端点 $i$，用变量 $t$ 维护左边 $firstLen$ 个元素的子数组的最大和，那么答案就是 $t + s[i + secondLen] - s[i]$。枚举完所有的 $i$，就可以得到候选答案。

假设 $secondLen$ 个元素的子数组在 $firstLen$ 个元素的子数组的左边，那么我们可以枚举 $firstLen$ 个元素的子数组的左端点 $i$，用变量 $t$ 维护左边 $secondLen$ 个元素的子数组的最大和，那么答案就是 $t + s[i + firstLen] - s[i]$。枚举完所有的 $i$，就可以得到候选答案。

最后，我们取两种情况下的候选答案的最大值即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 nums 的长度。

class Solution:
  def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
    n = len(nums)
    s = list(accumulate(nums, initial=0))
    ans = t = 0
    i = firstLen
    while i + secondLen - 1 < n:
      t = max(t, s[i] - s[i - firstLen])
      ans = max(ans, t + s[i + secondLen] - s[i])
      i += 1
    t = 0
    i = secondLen
    while i + firstLen - 1 < n:
      t = max(t, s[i] - s[i - secondLen])
      ans = max(ans, t + s[i + firstLen] - s[i])
      i += 1
    return ans

class Solution {
  public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0;
    for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {
      t = Math.max(t, s[i] - s[i - firstLen]);
      ans = Math.max(ans, t + s[i + secondLen] - s[i]);
    }
    for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {
      t = Math.max(t, s[i] - s[i - secondLen]);
      ans = Math.max(ans, t + s[i + firstLen] - s[i]);
    }
    return ans;
  }
}

class Solution {
public:
  int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
    int n = nums.size();
    vector<int> s(n + 1);
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0;
    for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {
      t = max(t, s[i] - s[i - firstLen]);
      ans = max(ans, t + s[i + secondLen] - s[i]);
    }
    for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {
      t = max(t, s[i] - s[i - secondLen]);
      ans = max(ans, t + s[i + firstLen] - s[i]);
    }
    return ans;
  }
};

func maxSumTwoNoOverlap(nums []int, firstLen int, secondLen int) (ans int) {
  n := len(nums)
  s := make([]int, n+1)
  for i, x := range nums {
    s[i+1] = s[i] + x
  }
  for i, t := firstLen, 0; i+secondLen-1 < n; i++ {
    t = max(t, s[i]-s[i-firstLen])
    ans = max(ans, t+s[i+secondLen]-s[i])
  }
  for i, t := secondLen, 0; i+firstLen-1 < n; i++ {
    t = max(t, s[i]-s[i-secondLen])
    ans = max(ans, t+s[i+firstLen]-s[i])
  }
  return
}