1218.最长定差子序列.md

1218.最长定差子序列

/*
 * @lc app=leetcode.cn id=1218 lang=typescript
 *
 * [1218] 最长定差子序列
 */

// @lc code=start
function longestSubsequence(arr: number[], difference: number): number {}

// @lc code=end

解法 1: 动态规划

• dp 是一个数组,j 表示数字第 i 位的数字
• dp[j] 在 i 之前,最后一位数字为 j 定差子序列的最大长度
• dp[j]=dp[j-dif]+1
• 边界:
  • dp[j-dif]如果为空,则表示没有当前数之前的等差数存在,直接以当前数开始,既长度为 1
  • 因为题目中的数会存在负数的情况,数组的索引不能为负数,题目中数的范围是 -10^4 ~ 10^4 ,这样每个数加上 10^5 就足够了.

function longestSubsequence(arr: number[], difference: number): number {
  const dp: number[] = []
  let [base, max] = [10 ** 5, 0]

  for (const n of arr) {
    const num = n + base
    if (num >= difference) dp[num] = (dp[num - difference] ?? 0) + 1
    max = Math.max(max, dp[num])
  }
  return max
}

使用哈希表

使用哈希表的好处是可以不用去单独处理负数

function longestSubsequence(arr: number[], difference: number): number {
  const dp: { [k: number]: number } = {}
  let max = 0

  for (const num of arr) {
    dp[num] = (dp[num - difference] ?? 0) + 1
    max = Math.max(max, dp[num])
  }
  return max
}

Case

test.each([
  { input: { arr: [1, 2, 3, 4], difference: 1 }, output: 4 },
  { input: { arr: [1, 3, 5, 7], difference: 1 }, output: 1 },
  { input: { arr: [1, 5, 7, 8, 5, 3, 4, 2, 1], difference: -2 }, output: 4 },
  { input: { arr: [2, -6, -3, -6, 2, 0], difference: -2 }, output: 2 },
  {
    input: {
      arr: [4, 12, 10, 0, -2, 7, -8, 9, -9, -12, -12, 8, 8],
      difference: 0,
    },
    output: 2,
  },
])('input: arr = $input.arr, difference = $input.difference', ({ input: { arr, difference }, output }) => {
  expect(longestSubsequence(arr, difference)).toEqual(output)
})