My Three C++ Solutions: DP, Binary Search and Lower_bound
Solution One:\n\n    class Solution {\n    public:\n        int maxEnvelopes(vector>& envelopes) {\n            int res = 0, n = envelopes.size();\n    \t\tvect
Solution One:\n\n    class Solution {\n    public:\n        int maxEnvelopes(vector<pair<int, int>>& envelopes) {\n            int res = 0, n = envelopes.size();\n    \t\tvector<int> dp(n, 1);\n    \t\tsort(envelopes.begin(), envelopes.end());\n    \t\tfor (int i = 0; i < n; ++i) {\n    \t\t\tfor (int j = 0; j < i; ++j) {\n    \t\t\t\tif (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {\n    \t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1);\n    \t\t\t\t}\n    \t\t\t}\n    \t\t\tres = max(res, dp[i]);\n    \t\t}\n    \t\treturn res;\n        }\n    };\n\nSolution Two:\n\n    class Solution {\n    public:\n        int maxEnvelopes(vector<pair<int, int>>& envelopes) {\n            vector<int> dp;\n    \t\tsort(envelopes.begin(), envelopes.end(), [](const pair<int, int> &a, const pair<int, int> &b){\n    \t\t\tif (a.first == b.first) return a.second > b.second;\n    \t\t\treturn a.first < b.first;\n    \t\t});\n    \t\tfor (int i = 0; i < envelopes.size(); ++i) {\n    \t\t\tint left = 0, right = dp.size(), t= envelopes[i].second;\n    \t\t\twhile (left < right) {\n    \t\t\t\tint mid = left + (right - left) / 2;\n    \t\t\t\tif (dp[mid] < t) left = mid + 1;\n    \t\t\t\telse right = mid;\n    \t\t\t}\n    \t\t\tif (right >= dp.size()) dp.push_back(t);\n    \t\t\telse dp[right] = t;\n    \t\t}\n    \t\treturn dp.size();\n        }\n    };\n\nSolution Three:\n\n    class Solution {\n    public:\n        int maxEnvelopes(vector<pair<int, int>>& envelopes) {\n            vector<int> dp;\n    \t\tsort(envelopes.begin(), envelopes.end(), [](const pair<int, int> &a, const pair<int, int> &b){\n    \t\t\tif (a.first == b.first) return a.second > b.second;\n    \t\t\treturn a.first < b.first;\n    \t\t});\n    \t\tfor (int i = 0; i < envelopes.size(); ++i) {\n    \t\t\tauto it = lower_bound(dp.begin(), dp.end(), envelopes[i].second);\n    \t\t\tif (it == dp.end()) dp.push_back(envelopes[i].second);\n    \t\t\telse *it = envelopes[i].second;\n    \t\t}\n    \t\treturn dp.size();\n        }\n    };
[]