This documentation is automatically generated by competitive-verifier/competitive-verifier
最長増加部分列(LIS)の長さを求める.
LIS(v, strict)
:配列 v
の最長増加部分列の長さを返す.strict
が true
の場合は狭義単調,false
の場合は広義単調の長さを返す.v
の要素数を $n$ とする.
#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> int LIS(const vector<T> &v, bool strict = true) {
vector<T> lis;
if(strict) {
for(T a : v) {
auto itr = lower_bound(lis.begin(), lis.end(), a);
if(itr == lis.end()) lis.emplace_back(a);
else
*itr = a;
}
}
else {
for(T a : v) {
auto itr = upper_bound(lis.begin(), lis.end(), a);
if(itr == lis.end()) lis.emplace_back(a);
else
*itr = a;
}
}
return lis.size();
}
#line 2 "dp/lis.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> int LIS(const vector<T> &v, bool strict = true) {
vector<T> lis;
if(strict) {
for(T a : v) {
auto itr = lower_bound(lis.begin(), lis.end(), a);
if(itr == lis.end()) lis.emplace_back(a);
else
*itr = a;
}
}
else {
for(T a : v) {
auto itr = upper_bound(lis.begin(), lis.end(), a);
if(itr == lis.end()) lis.emplace_back(a);
else
*itr = a;
}
}
return lis.size();
}