Longest Increasing Subsequence (最長増加部分列)
(DP/LongestIncreasingSubsequence.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "DP/LongestIncreasingSubsequence.hpp"

概要

最長増加列の長さを返す．

計算量

配列の長さをNとすると
O(NlogN)

tips

• 最長増加列の数え上げ : https://yukicoder.me/problems/no/992

Verified with

• test/yuki3784.test.cpp

Code

template<typename T>
int LongestIncreasingSubsequence(vector<T> v,bool strict=true){
    vector<T> lis;
    for(auto &x:v){
        typename vector<T>::iterator ite;
        if(strict) ite=lower_bound(begin(lis),end(lis),x);
        else       ite=upper_bound(begin(lis),end(lis),x);
        if(ite==end(lis)) lis.push_back(x);
        else              *ite=x;
    }
    return int(lis.size());
}

#line 1 "DP/LongestIncreasingSubsequence.hpp"
template<typename T>
int LongestIncreasingSubsequence(vector<T> v,bool strict=true){
    vector<T> lis;
    for(auto &x:v){
        typename vector<T>::iterator ite;
        if(strict) ite=lower_bound(begin(lis),end(lis),x);
        else       ite=upper_bound(begin(lis),end(lis),x);
        if(ite==end(lis)) lis.push_back(x);
        else              *ite=x;
    }
    return int(lis.size());
}

Back to top page