354. 俄罗斯套娃信封问题

354. 俄罗斯套娃信封问题

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int ans = 1;
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length != 2)
            return 0;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            @Override
            // 先按照长递增排序（当长相同时按照宽递减排序）
            public int compare(int[] e1, int[] e2) {
                if (e1[0] == e2[0]) {
                    return e2[1] - e1[1];
                } else {
                    return e1[0] - e2[0];
                }
            }
        });
        int[] dp = new int[envelopes.length];
        dp[0] = 1;
        for (int i = 1; i < envelopes.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}