[LIS]leetcode1218：最长定差子序列(medium)

题目：

题解：

思路：线性 dp

• 状态表示以及状态转移方程参考 300. 最长上升子序列。

代码如下：

class Solution {
public:
    // LIS 模型
    int longestSubsequence(vector& a, int diff) {
        // 用 hashmap 来记录状态，f[i]表示以数字i结尾的等差子序列的长度
        unordered_map f;
        int res=0;
        for(int x:a){
            // 状态转移：f[x]只能由它的上一个状态f[x-diff]推出来，而且这个f[x-diff]为上一个状态的最长长度
            // 若f[x-diff]不存在，即为0，这样f[x]=1表示以数字x结尾的等差子序列的长度为1
            f[x]=max(f[x],f[x-diff]+1);
            res=max(res,f[x]);
        }
        return res;
    }
};