# Clean C++ 11 Implementation with Explaination refered from @kamyu104

• It is easy to relate this problem with the previous LIS problem. But how to solve it under the 2 dimensional cases. The key ideas lay at that how we deal with the equal width but different hight cases.

A clever solution is to sort the pair<int,int> array according the width, if the width is equal, just sort by the height reversely.

Then we can get the following solutions :

``````class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
int size_ = envelopes.size();
if(size_ < 2)  return size_;
sort(envelopes.begin(), envelopes.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
if(a.first == b.first) {
return a.second > b.second;
}
else {
return a.first < b.first;
}
});
/** find the LIS of the height, as we have filtered the width equal cases **/
vector<int> result;
for (const auto& iter : envelopes) {
const auto target = iter.second;
auto cur = lower_bound(result.begin(), result.end(), target);
if (cur == result.end()) {
result.emplace_back(target);
} else {
*cur = target;
}
}
return result.size();
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.