LIS
- 最長増加部分列のこと
- 部分列において、狭義単調増加(a1 < a2 < a3 ... )
解説
verify✅
- Longest Increasing Subsequence
- D - トランプ挿入ソート
感想
- 配列Lは単調増加
- なので後端だけ見る or 二分探索で高速に更新箇所を決められる
- ※配列LはLISではないことに注意
関連問題
関数化
ll LIS(VI& A){
ll N = A.size();
VI L;
L.push_back(A[0]);
FOR(i, 1, N){
ll a = A[i];
if(L.back()<a){
L.push_back(a);
}else{
auto it = lower_bound(ALL(L), a);
*it = a;
}
}
return L.size();
}
LIS復元
ll index_of(VI& A, ll x){
return distance(A.begin(), lower_bound(A.begin(), A.end(), x));
}
VI LIS(VI& a) {
const int n = a.size();
VI A(n, inf);
VI id(n);
rep(i,n){
id[i] = index_of(A, a[i]);
A[ id[i] ] = a[i];
}
int m = *max_element(id.begin(), id.end());
VI b(m+1);
for (int i = n-1; i >= 0; --i)
if (id[i] == m){
b[m] = a[i];
m--;
}
return b;
}
int main(){
VI A = {5,3,7,4,1};
auto a = LIS(A);
debug(a);
return 0;
}
出力
{3, 4}
- 参考先のを自分用に書き換えたもの。補助配列idを使うことで正しく復元できている
- TODO verify用問題
広義単調LIS
- a1 <= a2 <= a3 ... とイコールを許す
ll LIS2(VI& A){
ll N = A.size();
VI V;
V.push_back(A[0]);
FOR(i, 1, N){
ll a = A[i];
if(V.back()<=a){
V.push_back(a);
}else{
auto it = upper_bound(ALL(V), a);
*it = a;
}
}
debug(V);
return V.size();
}
関連問題