354. 俄罗斯套娃信封问题

题目：

算法思想：
本题采用排序加动态规划的思想，其实本题跟一维数组的求最长递增子序列的题目类似，这题只是二维数组的求最长子序列。首先我们先将数组，按照第一列的顺序进行升序排序，然后第二列按照第一列如果相等的数，第二列降序排序，然后对第二列求最长递增子序列即可。

代码：

class Solution {
    public  static int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (int a[], int b[]) -> {
            if (a[0] == b[0]) {
                 return b[1]-a[1];
            }else {
                return a[0]-b[0];
            }

        });
        int dp[] = new int[envelopes.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    max = Math.max(dp[i], max);
                    continue;
                }
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25