原文链接: https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference
英文原文
Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.
A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
1 <= arr.length <= 105-104 <= arr[i], difference <= 104
中文题目
给你一个整数数组 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
通过代码
高赞题解
序列 DP + 哈希表
定义 $f[i][j]$（$j$ 非 $0$ 即 $1$） 为代表考虑前 $i$ 个数，且第 $i$ 个数的选择情况为 $j$ 时，得到的最长定差子序列长度。
最终答案为 $\max(f[n - 1][0], f[n - 1][1])$，同时我们有显然的初始化条件 $f[0][0] = 0$ 和 $f[0][1] = 1$。
不失一般性考虑 $f[i][j]$ 如何转移：
- $f[i][0]$：明确了第 $i$ 个不选，那么此时最大长度为前一个位置的结果。即有：
$$
f[i][0] = \max(f[i - 1][0], f[i - 1][1])
$$
$f[i][1]$：明确了第 $i$ 个要选，此时进行分情况讨论：
- $arr[i]$ 独立成为一个子序列，此时有：$f[i][1] = 1$；
- $arr[i]$ 接在某一个数的后面，由于给定了差值 $difference$，可直接算得上一位的值为 $prev = arr[i] - difference$，此时应当找到值为 $prev$，下标最大（下标小于 $i$）的位置，然后从该位置转移过来，即有：$f[i][1] = f[hash[prev]][1] + 1$;
容易证明：如果存在多个位置的值为 $prev$，从中选择一个下标最大的位置（下标小于 $i$）进行转移，结果相比于最优位置不会变差。因此我们「贪心」选择下标最大的位置（下标小于 $i$）即可，这引导我们在转移过程中使用「哈希表」记录处理过的位置的值信息。
综上，我们有：
$$
f[i][1] = \begin{cases}
1 & hash[arr[i] - difference] = -1 \
f[hash[prev]][1] + 1 & hash[arr[i] - difference] \neq -1
\end{cases}
$$
代码（使用数组充当哈希表的代码在 $P2$）：
[]class Solution { public int longestSubsequence(int[] arr, int d) { int n = arr.length; Map<Integer, Integer> map = new HashMap<>(); int[][] f = new int[n][2]; f[0][1] = 1; map.put(arr[0], 0); for (int i = 1; i < n; i++) { f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] = 1; int prev = arr[i] - d; if (map.containsKey(prev)) f[i][1] = Math.max(f[i][1], f[map.get(prev)][1] + 1); map.put(arr[i], i); } return Math.max(f[n - 1][0], f[n - 1][1]); } }
[]class Solution { int N = 40009, M = N / 2; public int longestSubsequence(int[] arr, int d) { int n = arr.length; int[] hash = new int[N]; Arrays.fill(hash, -1); int[][] f = new int[n][2]; f[0][1] = 1; hash[arr[0] + M] = 0; for (int i = 1; i < n; i++) { f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] = 1; int prev = arr[i] - d; if (hash[prev + M] != -1) f[i][1] = Math.max(f[i][1], f[hash[prev + M]][1] + 1); hash[arr[i] + M] = i; } return Math.max(f[n - 1][0], f[n - 1][1]); } }
- 时间复杂度：令 $n$ 为数组长度，共有 $n * 2$ 个状态需要被计算，每个状态转移的复杂度为 $O(1)$。整体复杂度为 $O(n)$
- 空间复杂度：$O(n)$
优化状态定义
不难发现，我们多定义一维状态来区分某个位置的值是否被选择，目的是为了正确转移出第 $i$ 位被选择的情况。
事实上，利用哈希表本身我们就能轻松做到这一点。
我们调整状态定义为：**$f[i]$ 为考虑前 $i$ 个数（第 $i$ 个数必选）时，得到的最长定差子序列长度。**
不失一般性考虑 $f[i]$ 该如何转移，分情况讨论：
- $arr[i]$ 独立成为一个子序列，此时有：$f[i] = 1$；
- $arr[i]$ 接在某一个数的后面，由于给定了差值 $difference$，可直接算得上一位的值为 $prev = arr[i] - difference$，此时应当找到 $arr[j]$ 为 $prev$ 的最新位置（下标最大，同时满足 $j < i$）当时的转移结果，在此基础上加一即可，即有：$f[i] = hash[prev] + 1$;
综上，我们有（$hash$ 初始化为 $0$）：
$$
f[i] = hash[prev] + 1
$$
代码（使用数组充当哈希表的代码在 $P2$）：
[]class Solution { public int longestSubsequence(int[] arr, int d) { int ans = 1; Map<Integer, Integer> map = new HashMap<>(); for (int i : arr) { map.put(i, map.getOrDefault(i - d, 0) + 1); ans = Math.max(ans, map.get(i)); } return ans; } }
[]class Solution { int N = 40009, M = N / 2; public int longestSubsequence(int[] arr, int d) { int ans = 1; int[] hash = new int[N]; for (int i : arr) { hash[i + M] = hash[i - d + M] + 1; ans = Math.max(ans, hash[i + M]); } return ans; } }
- 时间复杂度：令 $n$ 为数组长度，共有 $n$ 个状态需要被计算，每个状态转移的复杂度为 $O(1)$。整体复杂度为 $O(n)$
- 空间复杂度：$O(n)$
其他
意犹未尽？考虑加练如下「序列 DP」内容 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 354. 俄罗斯套娃信封问题 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
| 368. 最大整除子集 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 446. 等差数列划分 II - 子序列 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
| 583. 两个字符串的删除操作 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 673. 最长递增子序列的个数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 740. 删除并获得点数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
| 978. 最长湍流子数组 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 1035. 不相交的线 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 1143. 最长公共子序列 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 1473. 粉刷房子 III | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 1713. 得到子序列的最少操作次数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 36706 | 71394 | 51.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
