Longest Increasing Subsequence(最長増加部分列)
(dp/longest-increasing-subsequence.hpp)

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #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 のとき広義で求める.

計算量

• $O(N \log N)$

Verified with

• test/verify/aoj-dpl-1-d.test.cpp

Code

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();
}

Back to top page