Time: 20191006 Type: Medium
给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。
示例 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 < = a r r . l e n g t h < = 1 0 5 1 <= arr.length <= 10^5 1<=arr.length<=105 − 1 0 4 < = a r r [ i ] , d i f f e r e n c e < = 1 0 4 -10^4 <= arr[i], difference <= 10^4 −104<=arr[i],difference<=104
这道题可以用动态规划的方法来解，首先题目要求的是最长，需要往动态规划类问题上找答案。
动态规划要求我们定义状态，常规的定义f[i]表示以arr[i]元素结尾的等差数列的最大长度。
等差数列的性质决定了，我们在计算f[i]时，需要考虑的上一个元素是f[i-d]，如果f[i-d]存在，则f[i] = f[i - d] + 1，否则f[i] = 1。
即转移方程为：
f[i] = f[i-d] + 1 if f[i-d]存在，否则f[i] = 1下面这个是Python版本的代码，只需要简单的几行代码即可：
def longestSubsequence(self, arr: List[int], diff: int) -> int: res = {} for num in arr: res[num] = res[num - diff] + 1 if (num - diff) in res else 1 return max(res.values())2019.10 Update:
第一届PAT算法直播课培训班招募帖，欢迎点击查看详情、
END.
