# 1218. 最长定差子序列
### 题目地址(1218. 最长定差子序列)
### 题目描述
```
给你一个整数数组 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 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
```
### 前置知识
* 数组
* 动态规划
### 公司
* 腾讯
### 思路
最直观的思路是双层循环，我们暴力的枚举出以每一个元素为开始元素，以最后元素结尾的的所有情况。很明显这是所有的情况，这就是暴力法的精髓， 很明显这种解法会 TLE（超时），不过我们先来看一下代码，顺着这个思维继续思考。
#### 暴力法
```python
def longestSubsequence(self, arr: List[int], difference: int) -> int:
n = len(arr)
res = 1
for i in range(n):
count = 1
for j in range(i + 1, n):
if arr[i] + difference * count == arr[j]:
count += 1
if count > res:
res = count
return res
```
**复杂度分析**
* 时间复杂度：$O(N^2)$
* 空间复杂度：$O(N)$
#### 动态规划
上面的时间复杂度是 O(n^2)， 有没有办法降低到 O(n)呢？很容易想到的是空间换时间的解决方案。
我的想法是将`以每一个元素结尾的最长等差子序列的长度`统统存起来，即`dp[num] = maxLen` 这样我们遍历到一个新的元素的时候，就去之前的存储中去找`dp[num - difference]`, 如果找到了，就更新当前的`dp[num] = dp[num - difference] + 1`, 否则就是不进行操作（还是默认值 1）。
这种空间换时间的做法的时间和空间复杂度都是 O(n)。
### 关键点解析
* 将`以每一个元素结尾的最长等差子序列的长度`统统存起来
### 代码
```python
#
# @lc app=leetcode.cn id=1218 lang=python3
#
# [1218] 最长定差子序列
#
# @lc code=start
class Solution:
# 动态规划
def longestSubsequence(self, arr: List[int], difference: int) -> int:
n = len(arr)
res = 1
dp = {}
for num in arr:
dp[num] = 1
if num - difference in dp:
dp[num] = dp[num - difference] + 1
return max(dp.values())
# @lc code=end
```
**复杂度分析**
令 n 为数组长度
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
### 相关题目
* [3041. 修改数组后最大化数组中的连续元素数目](/leetcode-solution/hard/3041.maximize-consecutive-elements-in-an-array-after-modification.md)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1218.longest-arithmetic-subsequence-of-given-difference.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.