力扣1218.最长定差子序列

题目

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

​ 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

解题思路

​ 动态规划

1.常规的动态规划解题思路会超时，本题采用 哈希表+动态规划

2.二维dp数组，dp[i][1],dp[i][0] 分别表示第i个数选和不选

3.当前数 i不选时，当前dp的值取决于前一位两种情况的最大值 dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1])

4.当前数 i被选时有两种情况

​ ①默认初始值为1

​ ②与 arr[i]差值为 difference的值存在时获取此值的下标——利用哈希表，

​ dp[i][1]=Math.max(dp[hash.get(pre)][1]+1,dp[i][1]);

代码

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        if(arr.length==1){
            return 1;
        }
        int length=arr.length;
        int[][] dp=new int[length][2];
        Map<Integer,Integer> hash=new HashMap<>();
        hash.put(arr[0],0);
        dp[0][1]=1;

        for(int i=1;i<length;i++){
            dp[i][1]=1;
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);

            int pre=arr[i]-difference;
            if(hash.containsKey(pre)){
                dp[i][1]=Math.max(dp[hash.get(pre)][1]+1,dp[i][1]);
            }
            hash.put(arr[i],i);
        }
        
        return Math.max(dp[length-1][0],dp[length-1][1]);
    }
}