Longest Arithmetic Subsequence of Given Difference
Problem
Given an integer array arr and an integer difference, return the length of the longest subsequence where the difference between adjacent elements equals difference.
arr = [1, 5, 7, 8, 5, 3, 4, 2, 1], difference = -24def longest_subsequence(arr, difference):
dp = {}
best = 0
for x in arr:
dp[x] = dp.get(x - difference, 0) + 1
best = max(best, dp[x])
return bestfunction longestSubsequence(arr, difference) {
const dp = new Map();
let best = 0;
for (const x of arr) {
const prev = dp.get(x - difference) || 0;
dp.set(x, prev + 1);
if (dp.get(x) > best) best = dp.get(x);
}
return best;
}class Solution {
public int longestSubsequence(int[] arr, int difference) {
Map<Integer, Integer> dp = new HashMap<>();
int best = 0;
for (int x : arr) {
int len = dp.getOrDefault(x - difference, 0) + 1;
dp.put(x, len);
best = Math.max(best, len);
}
return best;
}
}int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int, int> dp;
int best = 0;
for (int x : arr) {
int len = dp[x - difference] + 1;
dp[x] = len;
best = max(best, len);
}
return best;
}Explanation
We want the longest subsequence where each step jumps by a fixed difference. Because the gap is fixed, the chain ending at a value x can only be extended from the value exactly one step before it, namely x - difference.
That makes a hash map perfect: dp[x] stores the length of the best valid subsequence that ends with value x.
We sweep left to right. For each value x, we look up dp[x - difference] (the chain that would lead into x), add one, and store it as dp[x]. If the predecessor was never seen, the lookup defaults to 0, so x starts a new chain of length 1.
We keep the running maximum and return it. Processing each element once gives a fast O(n) solution.
Example: arr = [1,5,7,8,5,3,4,2,1], difference = -2. The values 7, 5, 3, 1 each step down by 2, building dp up to 4, which is the answer.