old/longest-increasing-subsequence.inc.cpp

• View this file on GitHub
• Last update: 2020-01-08 18:35:19+09:00

Code

template <typename T>
vector<T> longest_strict_increasing_subsequence(vector<T> const & xs) {
    vector<T> l;  // l[i] is the last element of the increasing subsequence whose length is i + 1
    l.push_back(xs.front());
    for (auto && x : xs) {
        auto it = lower_bound(l.begin(), l.end(), x);
        if (it == l.end()) {
            l.push_back(x);
        } else {
            *it = x;
        }
    }
    return l;
}

template <typename T>
vector<T> longest_weak_increasing_subsequence(vector<T> const & xs) {
    vector<T> l;
    for (auto && x : xs) {
        auto it = upper_bound(l.begin(), l.end(), x);
        if (it == l.end()) {
            l.push_back(x);
        } else {
            *it = x;
        }
    }
    return l;
}

#line 1 "old/longest-increasing-subsequence.inc.cpp"
template <typename T>
vector<T> longest_strict_increasing_subsequence(vector<T> const & xs) {
    vector<T> l;  // l[i] is the last element of the increasing subsequence whose length is i + 1
    l.push_back(xs.front());
    for (auto && x : xs) {
        auto it = lower_bound(l.begin(), l.end(), x);
        if (it == l.end()) {
            l.push_back(x);
        } else {
            *it = x;
        }
    }
    return l;
}

template <typename T>
vector<T> longest_weak_increasing_subsequence(vector<T> const & xs) {
    vector<T> l;
    for (auto && x : xs) {
        auto it = upper_bound(l.begin(), l.end(), x);
        if (it == l.end()) {
            l.push_back(x);
        } else {
            *it = x;
        }
    }
    return l;
}

Back to top page