This documentation is automatically generated by competitive-verifier/competitive-verifier
#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();
}