1218. 最长定差子序列

解题思路

解法
1.分析题意，涉及到等差、等和等数学，首先想到动态规划算法，是否可以找到动态转移方程
2.经过推导，动态转移方程为dp[a[i]] = dp[a[i]-d]+!，最大值就是dp数组的最大值

解题遇到的问题

1.1双层for循环肯定超时
2.JDK1.8 新增了很多函数，要利用起来，例如map的getOrDefault
3.当实际解题中，遇到超时，可以想一下map降维

后续需要总结学习的知识点

是否有其他解法？

##解法1
class Solution {
    public static int longestSubsequence(int[] arr, int difference) {
        // 动态规划，用map进行降维处理
        HashMap<Integer, Integer> dp = new HashMap<>();
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            dp.put(arr[i], dp.getOrDefault(arr[i] - difference, 0) + 1);
            max = Math.max(max, dp.get(arr[i]));
        }
        return max;
    }
}