This documentation is automatically generated by online-judge-tools/verification-helper
#include "dp/longest-increasing-subsequence.hpp"
最長増加部分列(LIS)の長さを求める.
lis[i]
を、現状態で長さ $i$ 以下の増加部分列を作るときの最後の要素の最小値と定義する. このとき lis[i]
は常に単調増加になっている.
数列の要素を左からみる. 二分探索で lis[k]
が現在の要素以下(未満) となる最大の $k$ を求め, lis[k+1]
を現在の要素に書き換えることを繰り返すことで LIS を求めることができる.
ここでは実装しない(←実装しなさーい!)が別のアルゴリズムとして, lis[i]
を現状態で最後の要素が値 $i$ の増加部分列を作るときの最長の長さと定義する方法も存在する. 数列の要素を左から見ていって, 現在の値の要素以下(未満) で最大の lis[k]
$+ 1$ を求めることで更新出来て, これは BIT や セグメント木を使って効率的に求めることができる.
longest_increasing_subsequence(a, strict)
: 数列 a
の最長増加部分列の長さを求める.strict
が true
のとき狭義(厳密に増加する列), false
のとき広義で求める.template< typename T >
size_t longest_increasing_subsequence(const vector< T > &a, bool strict) {
vector< T > lis;
for(auto &p : a) {
typename vector< T >::iterator it;
if(strict) it = lower_bound(begin(lis), end(lis), p);
else it = upper_bound(begin(lis), end(lis), p);
if(end(lis) == it) lis.emplace_back(p);
else *it = p;
}
return lis.size();
}
#line 1 "dp/longest-increasing-subsequence.hpp"
template< typename T >
size_t longest_increasing_subsequence(const vector< T > &a, bool strict) {
vector< T > lis;
for(auto &p : a) {
typename vector< T >::iterator it;
if(strict) it = lower_bound(begin(lis), end(lis), p);
else it = upper_bound(begin(lis), end(lis), p);
if(end(lis) == it) lis.emplace_back(p);
else *it = p;
}
return lis.size();
}