[leetcode] 1218. Longest Arithmetic Subsequence of Given Difference

[leetcode] 1218. Longest Arithmetic Subsequence of Given Difference

Description

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.

Example 1:

Input: arr = [1,2,3,4], difference = 1Output: 4Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

Input: arr = [1,3,5,7], difference = 1Output: 1Explanation: The longest arithmetic subsequence is any single element.

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2Output: 4Explanation: The longest arithmetic subsequence is [7,5,3,1].

Constraints:

1 <= arr.length <= 10^5-10^4 <= arr[i], difference <= 10^4

分析

题目的意思是：求给定数组的最长等差子序列，其中差值给定。这道题我用dp数组做了一下，超时了，后面发现只需要用字典当成dp就可以了，简直哭晕。 如果之前做过最长递减子序列就比较容易上手了,递推公式

dp[num]=dp[num-difference]+1

以num结尾的最长序列等于以num-difference为结尾的子序列长度+1就行了。

代码

class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: d=collections.defaultdict(int) res=1 for num in arr: d[num]=d[num-difference]+1 res=max(res,d[num]) return res

参考文献

​​【LeetCode】1218. Longest Arithmetic Subsequence of Given Difference​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。