dp/longest_increasing_subsequence.hpp

• View this file on GitHub
• Last update: 2024-06-25 03:00:09+09:00
• Include: #include "dp/longest_increasing_subsequence.hpp"

Verified with

• verify/aoj/aoj_dpl_1_d.test.cpp

Code

template<class T>
int longest_increasing_subsequence(const vector<T> &A) {
    vector<T> lis;
    for(const auto& p : A) {
        // 狭義
        auto it = lower_bound(lis.begin(), lis.end(), p);
        if(lis.end() == it) lis.push_back(p);
        else *it = p;
    }
    return lis.size();
}

#line 1 "dp/longest_increasing_subsequence.hpp"
template<class T>
int longest_increasing_subsequence(const vector<T> &A) {
    vector<T> lis;
    for(const auto& p : A) {
        // 狭義
        auto it = lower_bound(lis.begin(), lis.end(), p);
        if(lis.end() == it) lis.push_back(p);
        else *it = p;
    }
    return lis.size();
}

Back to top page