原题地址
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;
}
};
