“Longest arithmetic subsequence of given difference, dp”
题干
给你一个整数数组 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
题解
可以先看一道类似的题目leecode-300，最长上升子序列：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
这一题使用动态规划的思路，状态转移方程为：
\[dp[i] = max(dp[j]) + 1, 0 \le j < i, num[j] < num[i]\]import java.util.Arrays;
public class Solution {
/**
* 给定一个无序的整数数组，找到其中最长上升子序列的长度
*
* @param nums 无序的整数数组
* @return 最长上升子序列的长度
*/
private static int lengthofLIS(int[] nums) {
// dp[i]是以nums[i]结尾的最长升序序列长度
int[] dp = new int[nums.length];
// 用于存储答案
int res = 0;
// 求最大值，初始化为最小值
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
// 条件：递增
// 状态转化：dp[i]=max{dp[i],dp[j]+1}
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
// res是max(dp[i]), i∈[0,n-1],即所有可能的升序序列里最大的
res = Math.max(res, dp[i]);
}
return res;
}
}
本题特殊的地方在于，上升的间隔也被指定了（ difference ），因此可以维护一个字典 dp<k,v> ，其中 v = dp[k] 表示以 v = nums[i] 结尾的最长定差子序列长度，具体算法如下：
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int res = 0;
Map<Integer, Integer> dp = new HashMap<Integer, Integer>();
for (int v : arr) {
dp.put(v, dp.getOrDefault(v - difference, 0) + 1);
res = Math.max(res, dp.get(v));
}
return res;
}
}
