DP + BINARY SEARCH Solution
\n# Approach\nSort the envelopes based on their widths in ascending order. If two envelopes have the same width, sort them in descending order of their heights.
\n# Approach\nSort the envelopes based on their widths in ascending order. If two envelopes have the same width, sort them in descending order of their heights. This sorting is done using a custom comparator function passed to the sort function.\n\nExtract the heights of the sorted envelopes and store them in the ans vector.\n\nDefine a helper function lis that takes the ans vector and its size n as input and returns the length of the longest increasing subsequence.\n\nInitialize a result vector and push the first element of ans into it.\n\nIterate through the remaining elements of ans starting from index 1.\n\nIf the current element is greater than the last element in the result vector, it can be nested inside the envelopes encountered so far. Hence, push the current element to the result vector.\n\nIf the current element is not greater, find the index where it can be placed in the result vector using the lower_bound function. Update the element at that index with the current element.\n\nFinally, return the size of the result vector, which represents the length of the longest increasing subsequence.\n\nIn the maxEnvelopes function, call the lis function with the ans vector and its size, and return the result.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:0(NLOGN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:0(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int lis(vector<int>& ans, int n) {\n        if (n == 0) {\n            return 0;\n        }\n        \n        vector<int> result;\n        result.push_back(ans[0]);\n        \n        for (int i = 1; i < n; i++) {\n            if (ans[i] > result.back()) {\n                result.push_back(ans[i]);\n            }\n            else {\n                int index = lower_bound(result.begin(), result.end(), ans[i]) - result.begin();\n                result[index] = ans[i];\n            }\n        }\n        \n        return result.size();\n    }\n    \n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        // SORT THE VECTOR\n        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);\n        });\n        \n        vector<int> ans;\n        for (auto i : envelopes) {\n            ans.push_back(i[1]);\n        }\n        \n        int n = ans.size();\n        return lis(ans, n);\n    }\n};\n\n```
['Array', 'Binary Search', 'Dynamic Programming', 'C++']