Leetcode|线性序列|354.俄罗斯套娃信封问题

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

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