# 1027. Longest Arithmetic Sequence

Given an array `A` of integers, return the length of the longest arithmetic subsequence in `A`.

Recall that a  subsequence  of `A` is a list `A[i_1], A[i_2], ..., A[i_k]` with `0 <= i_1 < i_2 < ... < i_k <= A.length - 1`, and that a sequence `B` is  arithmetic  if `B[i+1] - B[i]` are all the same value (for `0 <= i < B.length - 1`).

Example 1:

``````Input: A = [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
``````

Example 2:

``````Input: A = [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
``````

Example 3:

``````Input: A = [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
``````

Constraints:

• `2 <= A.length <= 1000`
• `0 <= A[i] <= 500`

``````class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
int res = 0, n = A.size();
vector<vector<int>> dp(n, vector<int>(2000));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int diff = A[i] - A[j] + 1000;
dp[i][diff] = dp[j][diff] + 1;
res = max(res, dp[i][diff]);
}
}
return res + 1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1027

https://leetcode.com/problems/longest-arithmetic-subsequence/

https://leetcode.com/problems/longest-arithmetic-subsequence/discuss/274611/JavaC%2B%2BPython-DP

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation