【线性 dp】B016

一、Problem

给定一个整数数组 A，返回 A 中最长等差子序列的长度。

回想一下，A 的子序列是列表 A[i_1], A[i_2], …, A[i_k] 其中 0 <= i_1 < i_2 < … < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

输入：[20,1,15,3,10,5,8] 输出：4 解释： 最长的等差子序列是 [20,15,10,5]。

提示：

2 <= A.length <= 2000 0 <= A[i] <= 10000

二、Solution

方法一：dp

定义状态： $f[i][d]$ 表示数组区间 $[0,i]$ 中，公差为 d 的最长等差数列长度 思考初始化： $f[0:][0:]=0$ 思考状态转移方程： 如果 $A[i]-A[j]=d，f[j][d]!=0$，则有 $f[i][d]=f[j][d]+1$否则，$f[i][d]=2$ 思考输出：$max(f[0:][0:])$

如果不用 map，那么就要根据数据范围将公差为负数的情况转为正数，再做状态转移

class Solution { public: int longestArithSeqLength(vector<int>& A) { int n = A.size(), ans = 1; vector<unordered_map<int,int>> f(n); for (int i = 1; i < n; i++) for (int j = 0; j < i; j++) { int d = A[i] - A[j]; if (f[j][d]) f[i][d] = f[j][d] + 1; else f[i][d] = 2; ans = max(ans, f[i][d]); } return ans; } };

复杂度分析

时间复杂度：$O(n^2)$，空间复杂度：$O(n)$，