网站每年要多少钱,什么网站可以免费发广告,动漫设计与制作属于什么类别,免费永久云服务器今日份题目#xff1a;
给你一个整数数组 arr 和一个整数 difference#xff0c;请你找出并返回 arr 中最长等差子序列的长度#xff0c;该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下#xff0c;通过删除一些元素或不删除任何…今日份题目
给你一个整数数组 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 105 -104 arr[i], difference 104
题目思路
这道题目我们假设选择当前数据那么到目前数值为止的最长序列长度应该为这个数值减去difference的那个数记录的长度加一所以得到状态转移方程dp[arr[i]]dp[arr[i]-difference]1;
注意由于arr[i]的数据范围有负数普通的数组不能用来记录有负数的情况故使用unordered_map记录dp值。
代码
class Solution
{
public:int longestSubsequence(vectorint arr, int difference) {int ans0;unordered_mapint,int dp; //假设结果序列选择当前数据那么到目前数值为止的最长序列长度为状态转移方程for(int i0;iarr.size();i) {dp[arr[i]]dp[arr[i]-difference]1; //状态转移方程ansmax(ans,dp[arr[i]]); //记录最大结果}return ans;}
};提交结果 欢迎大家在评论区讨论如有不懂的部分欢迎在评论区留言
更新不易宝子们点个赞支持下谢谢
