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

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

/*
 * @lc app=leetcode.cn id=689 lang=typescript
 *
 * [689] 三个无重叠子数组的最大和
 */

// @lc code=start
function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {}
// @lc code=end

解法 1: 记忆化搜索

function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
  const n = nums.length
  const sums = new Array(n).fill(0)
  for (let i = 0; i < nums.length; i++) {
    sums[i] = (sums[i - 1] ?? 0) + nums[i]
  }
  const dp = new Array(n).fill(0)
  for (let i = k - 1; i < n; i++) {
    dp[i] = sums[i] - (sums[i - k] ?? 0)
  }

  const cache: [number, number[]][][] = new Array(n).fill(0).map(() => [])
  const dfs = (i: number, depath = 0): [number, number[]] => {
    if (depath === 3) return [0, []]
    if (i < k - 1) return [0, []]

    if (cache[i][depath]) return cache[i][depath]

    const s2 = dfs(i - k, depath + 1)
    const s1 = dfs(i - 1, depath)

    if (s1[0] >= s2[0] + dp[i]) {
      cache[i][depath] = s1
    } else {
      cache[i][depath] = [s2[0] + dp[i], s2[1].concat(i)]
    }
    return cache[i][depath]
  }
  const res = dfs(nums.length - 1)

  return res[1].map(i => i - k + 1)
}

解法 2: 动态规划

• dp[i][j] 为前 i+1 个数中, j+1 个和最大的子数组,每个子数组长度为 k 并且不重叠.表示为一个长度为 j 的数组,数组中每个数 nums 中的下标,记录的是每个长度为 k 的子数组的最后一位.
• 最终返回时,需要将每个位置的下标减去 (k-1)
• 转移方程为: max(sum(dp[i-1][j]),sum(dp[i-k][j-1])+sums[i])
  • 要么包含当前的数,则为以当前数为结尾的 k 个数字和(既 sums[i])加上 0 ~ j-k 个数中最大的 j-1 个子数组既(dp[i-k][j-1])
  • 要么就是不包含当前的数,则为 0 ~ i-1 个数中最大的 j 个子数组既(dp[i-1][j])
  • 取两则中教大者,因为 dp 中保存的是下标数组,所以需要使用其中的下标数组取对应 sums 中的值相加,最后判断大小

例子: nums = [7, 13, 20, 19, 19, 2, 10, 1, 1, 19], k = 2
       dp[6][2]=[ 2, 4, 6 ]
         表示前 7 个数中,3 个和最大的子数组
         [ 2, 4, 6 ] 为这三个子数组的最后一位下标
         既这三个子数组分别是下标为 1~2, 3~4, 5~6

function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
  const n = nums.length
  const sums = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    sums[i] = (sums[i - 1] ?? 0) + nums[i]
    if (i >= k) sums[i] -= nums[i - k]
  }

  const dp: number[][][] = new Array(n).fill(0).map(() => [])
  const sum = (a: number, b: number) => a + sums[b]
  for (let i = k - 1; i < n; i++) {
    for (let j = 0; j < 3; j++) {
      const pre = dp[i - 1]?.[j] ?? []
      const cur = (dp[i - k]?.[j - 1] ?? []).concat(i)
      if (pre.reduce(sum, 0) >= cur.reduce(sum, 0)) {
        dp[i][j] = pre
      } else {
        dp[i][j] = cur
      }
    }
  }

  return dp[n - 1][2].map(i => i - k + 1)
}

Case

test.each([
  { input: { nums: [1, 2, 1, 2, 6, 7, 5, 1], k: 2 }, output: [0, 3, 5] },
  { input: { nums: [1, 2, 1, 2, 1, 2, 1, 2, 1], k: 2 }, output: [0, 2, 4] },
  { input: { nums: [4, 3, 2, 1], k: 1 }, output: [0, 1, 2] },
  {
    input: { nums: [7, 13, 20, 19, 19, 2, 10, 1, 1, 19], k: 3 },
    output: [1, 4, 7],
  },
  { input: { nums: [9, 8, 7, 6, 2, 2, 2, 2], k: 2 }, output: [0, 2, 4] },
])('input: nums = $input.nums, k = $input.k', ({ input: { nums, k }, output }) => {
  expect(maxSumOfThreeSubarrays(nums, k)).toEqual(output)
})