lc1027-最长等差数列

题目描述

• 给定一个数组，计算最长等差数列的长度

示例

输入：nums = [3,6,9,12]
输出：4
解释：3 6 9 12

输入：nums = [9,4,7,2,10]
输出：3
解释：4 7 10

输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：20 15 10 5

题解

• 思路：DP
  • f(i,j): 以 i 结尾，公差为 j
  • 结果至少为 2
  • 转移方程：f[i][j] = max(f[i][j], f[k][j] + 1) k<i

func longestArithSeqLength(nums []int) int {n := len(nums)f := make([]map[int]int, n)res := 2for i := 0; i < n; i ++ {for k := 0; k < i; k ++ {j := nums[k] - nums[i]if f[i] == nil { f[i] = map[int]int{} }if f[k] == nil { f[k] = map[int]int{} }if _, ok := f[i][j]; !ok {f[i][j] = 2}if _, ok := f[k][j]; ok {f[i][j] = max(f[i][j], f[k][j] + 1)res = max(res, f[i][j])}}}return res
}