算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

算法沉淀——动态规划之子序列问题

• 01.最长定差子序列
• 02.最长的斐波那契子序列的长度
• 03.最长等差数列
• 04.���差数列划分 II - 子序列

  01.最长定差子序列

  题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

  给你一个整数数组 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 public: int longestSubsequence(vector unordered_map hash[arr[i]]=hash[arr[i]-difference]+1; ret=max(ret,hash[arr[i]]); } return ret; }};public: int lenLongestFibSubseq(vector int n=arr.size(); unordered_map for(int j=1;j int x=arr[i]-arr[j]; if(xpublic: int longestArithSeqLength(vector unordered_map for(int j=i+1;j int x=2*nums[i]-nums[j]; if(hash.count(x)) dp[i][j] = dp[hash[x]][i] + 1; ret=max(ret,dp[i][j]); } hash[nums[i]]=i; } return ret; }};public: int numberOfArithmeticSlices(vector int n=nums.size(); unordered_map for(int i=1;i long long x=(long long)nums[i]*2-nums[j]; if(hash.count(x)) for(int& k:hash[x]) if(k