689.三个无重叠子数组的最大和

链接：689.三个无重叠子数组的最大和
难度：Hard
标签：数组、动态规划
简介：给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。

题解 1 - python

• 编辑时间：2023-11-19
• 执行用时：100ms
• 内存消耗：24.2MB
• 编程语言：python
• 解法介绍：dp[i]表示以当前为最后一个数组时的最大值。

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        sums = [0]
        for num in nums: sums.append(num + sums[-1])
        dp1 = [(0, 0)] * (n + 1)
        for i in range(0, n - k + 1):
            if dp1[i][0] < sums[i + k] - sums[i]:
                dp1[i + 1] = (sums[i + k] - sums[i], i)
            else:
                dp1[i + 1] = dp1[i]
        dp2 = [(0, 0, 0)] * (n + 1)
        for i in range(k, n - k + 1):
            if dp2[i][0] < sums[i + k] - sums[i] + dp1[i - k + 1][0]:
                dp2[i + 1] = (sums[i + k] - sums[i] + dp1[i - k + 1][0], dp1[i - k + 1][1], i)
            else:
                dp2[i + 1] = dp2[i]
        dp3 = [(0, 0, 0, 0)] * (n + 1)
        for i in range(k * 2, n - k + 1):
            if dp3[i][0] < sums[i + k] - sums[i] + dp2[i - k + 1][0]:
                dp3[i + 1] = (sums[i + k] - sums[i] + dp2[i - k + 1][0], dp2[i - k + 1][1], dp2[i - k + 1][2], i)
            else:
                dp3[i + 1] = dp3[i]
        return dp3[n - k + 1][1:]

题解 2 - typescript

• 编辑时间：2021-12-08
• 执行用时：80ms
• 内存消耗：42MB
• 编程语言：typescript
• 解法介绍：滑动窗口，记录每次的最大值比较。

function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
  const n = nums.length;
  let sum1 = 0,
    max1 = 0,
    idx1 = 0;
  let sum2 = 0,
    max2 = 0,
    idx2 = 0,
    idx2_1 = 0,
    idx2_2 = 0;
  let sum3 = 0,
    max3 = 0,
    idx3 = 0;
  let idx = 0;
  idx1 = idx;
  for (let i = idx, end = idx + k; i < end; i++, idx++) max1 = sum1 += nums[i];
  idx2_2 = idx2 = idx;
  for (let i = idx, end = idx + k; i < end; i++, idx++) max2 = max1 + (sum2 += nums[i]);
  idx3 = idx;
  for (let i = idx, end = idx + k; i < end; i++, idx++) max3 = max2 + (sum3 += nums[i]);
  const ans = [idx1, idx2, idx3];
  for (; idx < n; idx++) {
    sum1 = sum1 + nums[idx - 2 * k] - nums[idx - 3 * k];
    sum2 = sum2 + nums[idx - 1 * k] - nums[idx - 2 * k];
    sum3 = sum3 + nums[idx - 0 * k] - nums[idx - 1 * k];
    if (max1 < sum1) {
      max1 = sum1;
      idx1 = idx - 3 * k + 1;
    }
    if (max2 < max1 + sum2) {
      max2 = max1 + sum2;
      idx2 = idx - 2 * k + 1;
      idx2_1 = idx1;
      idx2_2 = idx2;
    }
    if (max3 < max2 + sum3) {
      max3 = max2 + sum3;
      idx3 = idx - 1 * k + 1;
      ans[0] = idx2_1;
      ans[1] = idx2_2;
      ans[2] = idx3;
    }
  }
  return ans;
}