LIS (最長増加部分列)
Last updated：2018-04-15 19:56:28
Tweet
Category:DP,
Tag：
LIS
概要
列$a$の最長増加部分列(Longest Increasing Subsequnce; LIS)を求める．
$a$の長さ$k$の増加部分列は，$i_1 < i_2 < \cdots < i_k$で$a_{i_1} < a_{i_2} < \cdots < a_{i_k}$なる部分列$\{a_{i_1}, a_{i_2}, \cdots, a_{i_k}\}$をいう．
計算量
$O(N\log N)$
使い方
std::vector<int>型の列を渡すとそのLISの長さを返す．
std::vector<int> a;
// aを初期化
// aのLISの長さを取得
int k = LIS(a);
実装例