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.

&nbsp;
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].


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	-104 &lt;= arr[i], difference &lt;= 104


class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = defaultdict(int)
        for num in arr:
            if num - difference in d:
                d[num] = d[num - difference] + 1
            else:
                d[num] = 1
        return max((d[x] for x in d))
class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int max = 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            // find the target element using the current element and the given difference
            int target = arr[i] - difference;
            // find if an AP for the target element exists in map and its length (else default to 1 - each element is an AP)
            int currAns = map.getOrDefault(target, 0) + 1;
            // add the current answer to the map
            // the amswer will override any previous answers with the same key (with an equal or greater answer)
            // for eg, in this case: .......X.....X
            // here X is the same number but the 2nd X will have an equal or larger AP sequence (logically)
            map.put(arr[i], currAns);
            // get max answer
            max = Math.max(max, currAns);
        }
        return max;
    }
}
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        
        int n = arr.size();
        
        unordered_map<int,int>mp;
        multiset<int>s;
        int ans = 1;
        
        for(int i=0;i<n;i++)
        {
            int req = arr[i] - difference;
            auto it = s.find(req);
            s.insert(arr[i]);
            
            if(it == s.end())
            {
                continue;    
            }
            else
            {
                mp[arr[i]] = mp[req] + 1;
                ans = max(ans,mp[arr[i]] + 1);
            }
        }
        
        return ans;
    }
};
var longestSubsequence = function(arr, difference) {
    const map = new Map()
    let max = 0
    for(let num of arr) {
        const prev = map.has(num - difference) ? map.get(num -difference) : 0
        const val = prev + 1
        map.set(num, val)
        max = Math.max(max, val)
    }
    return max
};
Longest Arithmetic Subsequence of Given Difference