力扣每日一题2021-11-05最长定差子序列

• 1218.最长定差子序列
• • 题目描述
  • 思路：动态规划+哈希表
  • • Java实现
    • Python实现

最长定差子序列

当前数字num能构成的最长定差子序列，由上一个num-difference能够成的最长定差子序列的长度决定。

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map map = new HashMap<>();
        int ans = 1;
        for (int num : arr) {
            int val = map.getOrDefault(num-difference, 0);
            map.put(num, ++val);
            ans = Math.max(ans, val);
        }
        return ans;
    }
}

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = defaultdict(int)
        for num in arr:
            d[num] = d[num-difference] + 1
        return max(d.values())