题解 | 信封嵌套问题

#include <vector>
class Solution {
  public:
    /**
        将数组从小到进行排列，前面的长度一定小于等于后面的长度，从前往后更新长度即可，继承最长的可继承长度
     */
    int maxLetters(vector<vector<int> >& letters) {
        sort(letters.begin(), letters.end(),
        []( vector<int>& a, vector<int>& b) {   //传入数组里的元素进行比较
            if (a[0] == b[0])return a[1] > b[1];
            return a[0] < b[0];
        });

        vector<int> dp(letters.size(), 1);
        int maxlen = 1;

        for(int i=1; i<letters.size(); i++){
            for(int j=0; j<i; j++){
                if(letters[i][0] > letters[j][0] && letters[i][1] > letters[j][1])
                {
                    dp[i] = max(dp[i], dp[j]+1);
                    maxlen = max(maxlen, dp[i]);
                }
            }
        }

        return maxlen;
    }
};