题目

给你一个整数数组 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 <= 10^5
-10^4 <= arr[i], difference <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference

一、解题思路

假设给定数组为 [1,5,3,6,5,7]，等差 d=2，辅助数组为 dp，求解的过程如下：

遍历到 1，发现 1-2=-1 不在 dp 数组，记录 dp[1] = 1，表示以 1 结尾的等差数列只有 1 个数；
遍历到 5，发现 5-2=3 不在 dp 数组，记录 dp[5]=1；
遍历到 3，发现 3-2=1 在 dp 数组且以 1 结尾的等差数列长度为 1，所以，记录 dp[3]=dp[3-2]+1=2，表示以 3 结尾的等差数列长度为 2；
遍历到 6，发现 6-2=4 不在 dp 数组，记录 dp[6]=1；
遍历到 5，发现 5-2=3 在 dp 数组，记录 dp[5]=dp[5-2]+1=3；
遍历到 7，发现 7-2=5 在 dp 数组，记录 dp[7]=dp[7-2]+1=4；
取 dp 数组中的最大值，即 4，所以，最长等差子序列的长度为 4。
这其实就是动态规划的递推过程，所以，我们可以定义动态规划如下：

状态定义：dp[x] 表示以 x 结尾的最长等差子序列的长度；
状态转移：dp[x]=dp[x-d]+1；

二、结果

1.注意点

利用辅助数组存储序列等差项的个数；

注意理解dp[x]=dp[x-d]+1的推到，存在一个等差的就+1；

2.C++代码

代码如下（示例）：

class Solution {
public:
    int longestSubsequence(vector<int> &arr, int difference) {
        int ans = 0;
        //创建dp数组来记录序列的个数
        unordered_map<int, int> dp;
        for (int v: arr) {
            dp[v] = dp[v - difference] + 1;
            ans = max(ans, dp[v]);
        }
        return ans;
    }
};

总结

题目完全可以用暴力去解决，但可能会超时，动态规划很难想到，要不断吸取经验，熟能生巧！！

加油加油，坚持坚持！！！

【LeetCode每日一题】（动态规划）1218. 最长定差子序列

题目

一、解题思路

二、结果

1.注意点

2.C++代码

总结