题目描述
题解
记 \(dp[i][d]\) 表示以 \(nums[i]\) 结尾的，公差为 \(d\) 的等差数列长度。对于满足 \(0 \le j \lt i\) 的 \(j\)，存在状态转移方程：$$dp[i][d] = max(dp[j][d]+1, dp[i][d])$$
其中 \(d=nums[i]-nums[j]\)， 由于 \(d\) 可能会小于0，由题给范围知 \(d \in [-500, 500]\)，可将其变换到 [0, 1000].
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size(), ans = 2;
vector<vector<int>> dp(n, vector<int>(1001, 1));
for (int i = 1;i < n;++i) {
for (int j = 0;j < i;++j) {
int d = nums[i] - nums[j] + 500;
dp[i][d] = max(dp[i][d], dp[j][d] + 1);
ans = max(ans, dp[i][d]);
}
}
return ans;
}
};
空间复杂度 \(O(n^2)\) ，时间复杂度 \(O(n^2)\)