1218.最长定差子序列

2021.11.5

1.题目介绍

也是和昨天题目一样简单暴力的题目吧

2.题目分析

算法：哈希表和动态规划
好久没有做算法题目，动态规划忘记了，这个题目其实算是非常经典的动态规划题目了，主要思路如下：

• 动态规划与暴力做法两种思想：

  暴力算法一般做数组类题目都是将当前的元素作为起始元素，向后遍历，时间复杂度O(n^2)，

  而动态规划有一个经典得到的思想是将当前的元素作为终止元素，因此对于当前元素就存在转移方程。

• 对于这道题目，我们设定dp[i]是以arr[i]结尾的最长子序列的长度，因此转移方程就是dp[i]=dp[i-1]+1,每一步选择最优策略。

• 这里我们对于数组arr进行倒序遍历，这样好处是序列中元素的次序保持不变，每次操作的时候都询问当前的集合中，对于arr[i]+difference是否存在，存在的话，将这个序列的长度取出+1，加在当前的元素key对应的value处。

3.代码实现

class Solution {
    public int longestSubsequence(int[] arr, int difference) 
    {
    	Map<Integer, Integer>mp=new HashMap<>();
    	int res=0;
    	//一遍插入一遍查找
        /*
        1.倒序查找已经保证了次序，所以在每个value处插入目前这个元素在这个difference的地方有多少次访问。
        2.旧元素处的数值顶掉旧value
        */ 
    	for(int i=arr.length-1;i>=0;--i)
    	{
    		int cnt=mp.getOrDefault(arr[i]+difference,0)+1;
            //System.out.println(cnt+"  "+arr[i]);
    		mp.put(arr[i],cnt);
    		res=Math.max(res, cnt);
    	}
    	return res;
    	}
}

QAQ感觉写的好白痴