俄罗斯套娃信封问题：求解最长上升子序列

给定一个二元信息组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组'俄罗斯套娃'信封（即可以把一个信封放到另一个信封里面）。

注意： 不允许旋转信封。

输入：

第一行为一个正整数 n（INT 范围内），代表信封总数。
接下来一行，包含 2*n 个正整数（INT 范围内）分别代表每个信封的宽度和高度。

输出：

能组成一组'俄罗斯套娃'信封组中所含的最多信封数。

样例输入：

5,4
6,4
6,7
2,3

样例输出：

思路：

将所有信封按照宽度从小到大排序，如果宽度相同，则按照高度从大到小排序。之后问题就转化为了求高度的最长上升子序列，可以用动态规划或者二分查找来解决。

时间复杂度： $O(n^2)$ 或 $O(n\log n)$

空间复杂度： $O(n)$

Python 代码：

def maxEnvelopes(envelopes):
    n = len(envelopes)
    envelopes.sort(key=lambda x: (x[0], -x[1]))  # 按照宽度升序，高度降序排序
    dp = [1] * n  # dp[i] 表示以第 i 个信封结尾的最长上升子序列长度
    for i in range(n):
        for j in range(i):
            if envelopes[j][1] < envelopes[i][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)