Classic LIS (DP — Longest Increasing Subsequence Sub-pattern)

// O(N^2): dp[i] = length of the longest increasing chain that ends at i.
int lisQuadratic(const vector<int>& a) {
    int n = a.size(), best = 0;
    vector<int> dp(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
        best = max(best, dp[i]);
    }
    return best;
}

// O(N log N): tails[k] = smallest last value of an increasing chain of length k + 1.
// tails is sorted; it gives the LENGTH only, not the chain itself.
int lisFast(const vector<int>& a) {
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);   // upper_bound for non-decreasing
        if (it == tails.end()) tails.push_back(x);   // longer than every chain so far
        else *it = x;                                // a smaller tail for that length
    }
    return tails.size();
}