给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于difference 。
子序列是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。
示例 2：
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。
示例 3：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。
提示：
1 <= arr.length <= 105
-104 <= arr[i], difference <= 104
今天这个题比较简单的，这里用到了动态规划，其实动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
如果你对动态规划一无所知或者有些不熟那你可以去—>动态递归详解.
看一下这个题的代码：
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int ans = 0;
int[] dp = new int[40001];
for (int num : arr) {
//因为difference+arr的最小值为-20000
//数组下标不可以为负，所以都加20000
dp[num + 20000] = dp[num + 20000 - difference] + 1;
//返回一个大的数
ans = Math.max(ans, dp[num + 20000]);
}
return ans;
}
}
如果你看不懂，那我们来举一个例子看看：
假设输入为[4,5,6,1,3,8]和2
首先遍历4，4-2=2，dp[4+20000]=dp[4+20000-2]+1;
此时dp[4+20000-2]=0，所以dp[4+20000]=1
然后遍历5，5-2=3，dp[5+20000]=dp[5+20000-2]+1
此时dp[5+20000-2]=0，所以dp[5+20000]=1
然后遍历6，6-2=4，dp[6+20000]=dp[6+20000-2]+1
此时dp[6+20000-2]=dp[4+20000]=1，所以dp[6+20000]=2
然后遍历1，1-2=-1，dp[1+20000]=dp[1+20000-2]+1
此时dp[1+20000-2]=0，所以dp[1+20000]=1
然后遍历3，3-2=1，dp[3+20000]=dp[3+20000-2]+1
此时dp[3+20000-2]=dp[1+20000]=1，所以dp[3+20000]=2
然后遍历8，8-2=6，dp[8+20000]=dp[8+20000-2]+1
此时dp[8+20000-2]=dp[6+20000]=2，所以dp[7+20000]=3
最后输出为：3
这下你应该懂了吧！很奇妙，不过这个前提是找子序列，也就是不改变元素顺序情况下！大家用之前一定要仔细读题，不要想当然哦，你现在再回头去看看代码，应该没问题吧！
最后我们在以一个例子结尾，可以先想想答案是多少，然后在看过程
输入为[4,5,6,1,3,7]和2
首先遍历4，4-2=2，dp[4+20000]=dp[4+20000-2]+1;
此时dp[4+20000-2]=0，所以dp[4+20000]=1
然后遍历5，5-2=3，dp[5+20000]=dp[5+20000-2]+1
此时dp[5+20000-2]=0，所以dp[5+20000]=1
然后遍历6，6-2=4，dp[6+20000]=dp[6+20000-2]+1
此时dp[6+20000-2]=dp[4+20000]=1，所以dp[6+20000]=2
然后遍历1，1-2=-1，dp[1+20000]=dp[1+20000-2]+1
此时dp[1+20000-2]=0，所以dp[1+20000]=1
然后遍历3，3-2=1，dp[3+20000]=dp[3+20000-2]+1
此时dp[3+20000-2]=dp[1+20000]=1，所以dp[3+20000]=2
然后遍历7，7-2=5，dp[7+20000]=dp[7+20000-2]+1
此时dp[7+20000-2]=dp[5+20000]=1，所以dp[7+20000]=2
输出为：2
欢迎大佬指点
持续更新中…