最大俄罗斯套娃信封组问题：算法与代码实现

问题描述：

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

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

**注意：**不允许旋转信封。

输入：

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

输出：

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

思路：

**排序：**首先将所有信封按照宽度升序排序，若宽度相同则按照高度降序排序。
**最长上升子序列：**然后在高度数组中寻找最长的上升子序列。
**结果：**最后子序列的长度即为最多能组成的'俄罗斯套娃'信封组中所含的最多信封数。

代码实现：

# 使用动态规划求解最长上升子序列
def maxEnvelopes(envelopes):
    n = len(envelopes)
    if n == 0:
        return 0
    envelopes.sort(key=lambda x: (x[0], -x[1])) # 宽度升序，高度降序
    dp = [1] * n  # dp[i] 表示以 envelopes[i] 结尾的最长上升子序列长度
    for i in range(1, n):
        for j in range(i):
            if envelopes[j][1] < envelopes[i][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

时间复杂度： $O(nlogn)$

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

其中 n 为信封的数量。

示例：

输入：
5
1 2 2 3 4 1 3 4 1 2

输出：
3

解释：

信封按照宽度和高度排序后为：[(1, 2), (2, 3), (3, 4), (4, 1), (1, 1)]。

最长的上升子序列为 [(1, 2), (2, 3), (3, 4)]，长度为 3。

因此，最多能组成 3 个俄罗斯套娃信封。