# 1218. Longest Arithmetic Subsequence of Given Difference

Given an integer array `arr` and an integer `difference`, return the length of the longest subsequence in `arr` which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals `difference`.

A subsequence is a sequence that can be derived from `arr` by deleting some or no elements without changing the order of the remaining elements.

Example 1:

``````Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].
``````

Example 2:

``````Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.
``````

Example 3:

``````Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].
``````

Constraints:

• `1 <= arr.length <= 105`
• `-104 <= arr[i], difference <= 104`

``````class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int res = 0;
unordered_map<int, int> dp;
for (int i : arr) {
dp[i] = 1 + dp[i - difference];
res = max(dp[i], res);
}
return res;
}
};
``````

Github 同步地址:

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

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/discuss/398196/C%2B%2B-O(n)-DP-using-Hashmap

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

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

×

Help us with donation