2D / envelopes (DP — Longest Increasing Subsequence Sub-pattern)

// 2-D chain, strictly bigger in both dimensions (Russian Doll Envelopes).
// Sort width ascending, and height DESCENDING for equal widths, then strict LIS on heights:
// two envelopes of the same width can never both be in one increasing run.
int maxNested(vector<vector<int>> env) {
    sort(env.begin(), env.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[0] != y[0] ? x[0] < y[0] : x[1] > y[1];
    });
    vector<int> tails;
    for (auto& e : env) {
        auto it = lower_bound(tails.begin(), tails.end(), e[1]);
        if (it == tails.end()) tails.push_back(e[1]);
        else *it = e[1];
    }
    return tails.size();
}