← all categories

Lis 5c58d50e

Longest strictly-increasing subsequence via patience sorting, with reconstruction. For longest non-decreasing, change the lower_bound to upper_bound.

Time: O(n \log n). tested

content/dp/lis.h

template <typename T>
vector<T> lis(vector<T> &a) {
    int n = (int)a.size();
    vector<T> tails;               // tails[i] = smallest possible tail value of an increasing subsequence of length i+1
    vector<int> tailIdx, par(n, -1);
    for (int i = 0; i < n; i++) {
        int p = (int)(lower_bound(tails.begin(), tails.end(), a[i]) - tails.begin());
        if (p == (int)tails.size()) { tails.push_back(a[i]); tailIdx.push_back(i); }
        else { tails[p] = a[i]; tailIdx[p] = i; }
        par[i] = (p > 0 ? tailIdx[p - 1] : -1);
    }

    vector<T> res;
    int at = tailIdx.empty() ? -1 : tailIdx.back();
    while (at != -1) { res.push_back(a[at]); at = par[at]; }
    reverse(res.begin(), res.end());
    return res;
}