Leetcode 646. Maximum Length of Pair Chain

原题地址

https://leetcode.com/problems/maximum-length-of-pair-chain/description/

题意&思路

给出n个形如a (a.first，a.second)的数对，a.first小于a.second, 当a.second<b.first时，b数对能接在a数对之后，求这样形成的序列的最大长度。
是LIS问题的一个变式，先排序，然后和普通的LIS做法一样。

代码

class Solution {
public:
    static bool compare(vector<int> &a,vector<int>& b){
        return a[0] <b[0];
    }
    
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(),compare);
        int n = pairs.size();
        int dp[n];
        for(int i = 0; i < n ; i++){
            dp[i]=1;
        }
        for(int i =1;i<n;i++){
            for(int j =0;j<i;j++){
                if(pairs[i][0]> pairs[j][1] && dp[j]+1 > dp[i]){
                    dp[i]=dp[j]+1;
                }
            }
        }
        int max=0;
        for(int i =0;i<n;i++){
            if(dp[i]>max){
                max=dp[i];
            }
        }
        return max;
    }
};