最長増加部分列

数列\(A\)を与えると、\(A\)の最長増加部分列の長さを求め、long longで返す

計算量は\(Ο(\vert A \vert log \vert A \vert)\)

github

long long LIS(std::vector<long long> A){
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    int N=A.size();
    std::vector<long long> D;
    for(int i=0;i<N;i++){
        int pos=distance(D.begin(),lower_bound(D.begin(), D.end(),A[i]));
        if(pos==D.size()){
            D.push_back(A[i]);
        }else{
            D[pos]=A[i];
        }
    }
    return D.size();
}

使用例

---

実行コード

#include <bits/stdc++.h>

long long LIS(std::vector<long long> A){/*省略*/}

int main(void){
    
    std::vector<long long> A={1,4,2,5,3},B={5,3,1,4,2};
    std::cout << LIS(A) << std::endl;
    std::cout << LIS(B) << std::endl;
    
    return 0;
}

出力

3
2

更新履歴

---

日時	内容
2023/06/29	ライセンスのコメントアウトを変更
2021/03/26	使用例を追加
2020/04/05	最長増加部分列を追加