LC 1218 [M] Longest Arithmetic Subsequence of Given Difference - ALawliet/algorithms GitHub Wiki

dp[i] = 1 + dp[i-k]

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        n = len(arr)
        
        dp = {}
        ans = 0
        
        for num in arr:
            target = num - difference
            
            if target not in dp:
                dp[num] = 1
            else:
                dp[num] = 1 + dp[target]
        
            ans = max(ans, dp[num])
            
        return ans