354. 俄罗斯套娃信封问题（动态规划）

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

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

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

• 1 <= envelopes.length <= 105
• envelopes[i].length == 2
• 1 <= wi, hi <= 105

这个题目是一个套娃问题，首先我们应该对数组进行排序，因为相同尺寸的信封不能够嵌套，所以我们按照每个子数组的第一个元素升序排序，第二个元素降序排序，这样这个问题就转化成了以第二个元素为主的最长上升子序列问题，这个思路好是好，但是想到前面快速排序需要耗费nlog₂n，后面的那个动态规划又是n²级别，c++语言时间会超限

那么我们就使用二分查找的策略

我们从头开始遍历，如果f[i]是指到第i个元素为止的最长上升子序列的最后一个元素，

那么到最后我们求得的f数组一定是一个单调递增的数组，而且f数组里的元素个数不大于envelopes.size()

如果envelopes[i]/[1]大于我们的f[i-1],那么f[i]=envelopes[i]/[1];

我们遍历envelopes[i]/[1]如果比f[i-1]小, 就在f[i]中找到那个刚好比他大的元素然后把它替换掉

因为被替换掉的元素不会影响最大子序列长度的个数（不信就自己验证一下）

#include
#include
#include
//先把信封按照宽度进行升序排序，然后按照高度进行降序排序，
//问题变成了在新的排好序的数组里寻找最长上升子序列
using namespace std;
class Solution {
public:
 

 int maxEnvelopes_plus(vector>& envelopes)
    {sort(envelopes.begin(),envelopes.end(),[](const auto s1,const auto s2){
        if(s1[0]!=s2[0])
        return s1[0]s2[1];
    });
    int n=envelopes.size();
    
    for(int i=0;idp = {envelopes[0][1]};;
    int answer=1;
    for(int i=1;idp.back())
    {
        dp.push_back(nums);
    }
    else
    {
        auto it=lower_bound(dp.begin(),dp.end(),nums);
        
       cout<<"the location of the iteration is"<<*it<{5,4},{6,4},{6,7},{2,3},{3,1},{5,3},{6,5},{7,2},{8,2}};

    vector>envelopes(9,vector(2,1));

    for(int i=0;i