Problem Name: 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
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.
Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].
Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.
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].
1 <= arr.length <= 105
-104 <= arr[i], difference <= 104
#1 Code Example with Python Programming
Copy The Code & Try With Live Editor
class Solution: def longestSubsequence(self, arr: List[int], d: int) -> int: dp = collections.Counter() for a in arr: dp[a] = max(dp[a], dp[a - d] + 1) return max(dp.values())