1027.最长等差数列.md

1027.最长等差数列

/*
 * @lc app=leetcode.cn id=1027 lang=typescript
 *
 * [1027] 最长等差数列
 */

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

解法 1: 动态规划

function longestArithSeqLength(nums: number[]): number {
  const dp = new Map<number, Map<number, number>>()
  let res = 1
  for (let num of nums) {
    let map = new Map<number, number>()
    for (let [a, b] of dp) {
      const d = num - a
      let max = 2
      if (b.has(d)) {
        max = b.get(d)! + 1
      }
      map.set(d, Math.max(map.get(d) ?? 0, max))
      res = Math.max(res, max)
    }
    dp.set(num, map)
  }
  return res
}

Case

test.each([
  { input: { nums: [3, 6, 9, 12] }, output: 4 },
  { input: { nums: [9, 4, 7, 2, 10] }, output: 3 },
  { input: { nums: [20, 1, 15, 3, 10, 5, 8] }, output: 4 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(longestArithSeqLength(nums)).toEqual(output)
})