动态规划-子序列问题——1218.最长定差子序列
1.题目解析
题目来源:1218.最长定差子序列——力扣
测试用例
2.算法原理
1.状态表示
本题可以看作是寻找一个等差序列,并且公差给出,这里并不是普通的使用一个dp表,而是将arr与dp表同时存储于一个哈希表,arr[i]映射dp[i],这样就可以只遍历符合等差序列的每个位置而不用遍历所有位置
2.状态转移方程
只需要找到符合等差序列的哈希表就直接对等差序列长度+1即可,即:hash[arr[i]] = hash[arr[i] - difference] + 1;
3.初始化
最小等差序列的长度为1,将第一个哈希表的位置置为1即可
4.填表顺序
从左到右只填写符合等差序列位置的值
5.返回值
返回哈希表的最大值
3.实战代码
class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size();unordered_map<int,int> hash;//arr[i] - dp[i]hash[arr[0]] = 1;int ret = 1;for(int i = 1;i < n;i++){hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret,hash[arr[i]]);}return ret;}
};