最長増加部分列

概要

数列の一部を、元の順序を保ったまま選んで狭義単調増加列を作るとき、その長さを最大化する問題。
動的計画法と二分探索を組み合わせて解ける。

ABCでは主にE問題以降で登場する。

典型問題例

• ABC006 D - トランプ挿入ソート

- 昇順のまま残せる最長部分列が最長増加部分列となる問題。

• Typical90 060 - Chimera

- 左右から最長増加部分列を求め、増加してから減少する部分列の最大長を求める問題。

コード例

最長増加部分列を求める（E問題レベル）

例えば、次の数列があったとする。

A = {1, 4, 3, 5, 2}

この場合、

B = {1, 4, 5}

という数列は狭義単調増加していて、しかも $A$ から一部の要素を元の順序を保って選ぶことで作られる。
このような $B$ を、$A$ の増加部分列という。
増加部分列の中で最も長いものを、最長増加部分列という。

最長増加部分列は、動的計画法を用いて求められる。
まず、$A$ と同じ長さの vector である len と、空の vector である vec を用意する。

len[i] = A[i] を末尾とする最長増加部分列の長さ - 1
vec[k] = 長さ k+1 の増加部分列の末尾として可能な最小値

$A$ の要素を先頭から $1$ つずつ処理する。
A[i] を処理するとき、以下の $2$ つの操作を行う。

$1$ つめに、vec の中で A[i] より小さい値が何個あるかを二分探索で求める。
その個数は len[i] に記録しておく。
これは、lower_bound で A[i] 以上となる最初の位置を探すことで求められる。

$2$ つめに、vec[len[i]] を A[i] に更新する。
len[i] が現在の vec の要素数と等しい場合は、末尾に A[i] を追加する。

以下に例を示す。
最初は、次の状態である。

A[0]=1 を処理する。
vec は空なので、len[0]=0 として vec の末尾に $1$ を追加する。

次に、A[1]=4 を処理する。
vec の中には $4$ より小さい値が $1$ 個あるので、len[1]=1 として vec の末尾に $4$ を追加する。

次に、A[2]=3 を処理する。
vec の中には $3$ より小さい値が $1$ 個あるので、len[2]=1 として vec[1] を $3$ に更新する。

次に、A[3]=5 を処理する。
vec の中には $5$ より小さい値が $2$ 個あるので、len[3]=2 として vec の末尾に $5$ を追加する。

最後に、A[4]=2 を処理する。
vec の中には $2$ より小さい値が $1$ 個あるので、len[4]=1 として vec[1] を $2$ に更新する。

最終的な vec の要素数が、最長増加部分列の長さである。
長さだけを求める場合、len を保存する必要はない。

実際の最長増加部分列を復元する場合は、len を後ろから調べる。
この例では最長増加部分列の長さが $3$ なので、まず len[i]=2 となる場所を後ろから探す。

• 最初に見つかるのは i=3 で、A[3]=5 を答えの末尾にする。
• 続いて len[i]=1 となる場所を前方へ戻りながら探す。最初に見つかる i=2 の A[2]=3 を使う。
• 続いて len[i]=0 となる場所を探し、i=0 の A[0]=1 を使う。

こうして、

{1, 3, 5}

という最長増加部分列を復元できる。
最長増加部分列は $1$ つとは限らないが、どれか $1$ つを求めればよい問題では、この方法で復元できる。

C++での実装例は、次のようになる。

vector<int> lis(const vector<int>& original) {
  int n = original.size();
  if (n==0) return {};
  vector<int> len(n);
  vector<int> vec;
  vec.reserve(n);
  for (int i=0; i<n; i++) {
    len[i] = distance(vec.begin(),lower_bound(vec.begin(),vec.end(),original[i]));
    if (len[i]==(int)vec.size()) vec.emplace_back(original[i]);
    else vec[len[i]] = original[i];
  }
  vector<int> result(vec.size());
  int idx = vec.size()-1;
  for (int i=n-1; i>=0; i--) {
    if (len[i]==idx) {
      result[idx] = original[i];
      idx--;
    }
  }
  return result;
}

各要素について lower_bound を $1$ 回行う。
復元のための後ろ向きの走査は $O(N)$ である。

• 時間計算量：$O(N\log N)$
• 空間計算量：$O(N)$

注意点

vec 自体が最長増加部分列とは限らない

最終的な vec は、各長さの増加部分列について、末尾として可能な最小値を記録したもの。
後から値が上書きされるため、vec の要素が元の数列に現れる順序と一致するとは限らない。

上の例では、最終的な vec は {1, 2, 5} となる。
しかし、元の数列では $2$ が $5$ より後ろにあるため、{1, 2, 5} は $A$ の部分列ではない。
実際の最長増加部分列が必要な場合は、len を用いて復元する。

関連アルゴリズム

動的計画法

少し小さい問題の答えを利用して、より大きい問題を順に解くアルゴリズム。
最長増加部分列では、各長さの増加部分列について、末尾の最小値を順に更新する。

二分探索

条件を満たす境界を高速に探すアルゴリズム。
最長増加部分列では、vec の中で現在の値以上となる最初の位置を探すために使う。

バックトレース

終了状態から逆向きにたどり、具体的な選び方などを復元する方法。
最長増加部分列そのものを復元するために使う。

最長共通部分列

$2$ つの数列または文字列の一部を、順序を保ったまま選び、同じ列を作るときの最大長を求める問題。
最長共通部分列を、最長増加部分列のアルゴリズムへ帰着して解くこともできる。