求最长等差子序列

[liuyingbin19222]

• [3,6,9,12] 数列中最长子序列是[3,6,9,12]，问题是给定一个数列，求最长子序列; 解法： 使用unordered_map<int,int> 来记录遍历顺序i和差值dis,通过两个for循环，内层循环中的dp[j][dis] == dp[i][dis]的情况下，说明内层循环中有等于外层循环的值，这样dp[i][dis] = dp[j][dis] + 1; 如果不等于的话，令ret = 2 ; 最后在内层循环中取值ret = max(ret, dp[i][dis]) ;最后return ret;

class Solution {
    private:
        int m;
public:

    int longestArithSeqLength(vector<int>& A) {
        /*
            通过记录差值来求出最长等差子数列;
        */
        m = A.size();
        if(m == 0) return 0;
        vector<unordered_map<int,int>> dp(m);
        // map<int,int> writeMap;
        int ret = 1;
        for(int i = 0;i < m; ++i){
            for(int j = 0;j < i; ++j){
                int dis = A[i] - A[j];
                if(dp[j][dis]) { dp[i][dis] = dp[j][dis] + 1; }
                else  { dp[i][dis] = 2;}
                ret = max(dp[i][dis],ret);      
            }
        }
        return ret;
    }
};

[liuyingbin19222]

这里面用到的一个数据结构是unordered_map<int,int> 数据结构，unordered_map 数据结构是无序map , 类似于java 中的hash_map , 在空间复杂度方面，小于map ; unordered_map底层实现是红黑树;