本文共 1021 字，大约阅读时间需要 3 分钟。

给你一个整数数组 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

解题思路

简单的动态规划，假设当前位置$i$的元素$arr[i]$结果的最长定差子序列是$f(arr[i])$，那么我们只需要判断$arr[i]-dif$在此之前有没有出现过即可。如果出现过

• $f(arr[i])=f(arr[i]-dif)+1$

否则的话

• $f(arr[i])=1$

class Solution:    def longestSubsequence(self, arr: List[int], dif: int) -> int:        mem, res = {
   }, 1        for i in arr:            if i - dif in mem:                mem[i] = mem[i-dif] + 1            else:                mem[i] = 1            res = max(res, mem[i])        return res

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/102474282 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！