1. 最長増加部分列問題

最長増加部分列問題 (LIS = Longest Increasing Subsequence) は，与えられた数列 $A = (a_0, a_1, \dots, a_{n - 1})$ の部分列であって， 単調増加であるもののうち最長のもの，ないし，その長さを求める問題．

2. 長さだけで良い場合

列 $B = (b_0, b_1, \dots, b_{m - 1})$ を次のように構築する．

2.1. 狭義単調列の場合

  • 最初は，$B = ()$.
  • $i = 0, 1, …, n - 1$ の順に，次を実行．
    • $a_i \leq b_k$ となる最小の $k$ を二分探索で求める．C++ なら次のコード: 
        k = lower_bound(ALL(B), a[i]) - B.begin();
      • このような $k$ が存在しない場合には，$a_i$ を $B$ に加える．($B$ の長さが 1 増える．)
      • 存在する場合には，$b_k$ を $a_i$ で置き換える． ($a_i = b_k$ なら何もしないことになる)
  • 作成された $B$ の長さが，求める長さになる．

途中の段階 ($a_i$ を処理したとき) の $b_k$ は，「$(a_0, \dots, a_i)$ の長さ $k$ の増加列の末項の最小値」 になっている．

2.2. 広義単調列の場合

上とほぼ同じだが，条件「$a_i \leq b_k$」を「$a_i < b_k$」 に差し替える． C++ なら次のコード:

  k = upper_bound(ALL(B), a[i]) - B.begin();

3. 列を 1 つ求めたい場合

上記の構築の場合，どの $a_i$ についても，「それが LIS に入るならば，その前の項が何であるか」は決まっている． これを記録していくようにする．

  • $B$ と同時に，同じ長さの列 $J$ も作っていく．$b_k$ が，「$i$ まで見たときにもっとも効率の良い長さ $k$ の増加列の末項の値」であるのに対し，$j_k$ は，「$i$ まで見たときにもっとも効率の良い長さ $k$ の増加列の末項の $A$ における添字」である．すなわち，$a_{j_k} = b_k$ が成り立つ．
  • (全体として) 長さ $n$ の配列 $C$ を作る．$c_i$ は，$a_i$ が LIS に入る場合の，1つ前の項の $A$ における添字である．

具体的な手順は以下の通り．

  • 最初は，$B = ()$，$J = ()$.
  • $i = 0, 1, …, n - 1$ の順に，次を実行する．
    • この時点で，$B = (b_0, \dots, b_m)$，$J = (j_0, \dots, j_m)$ であるとする．
    • $a_i \leq b_k$ となる (広義単調列なら，$a_i < b_k$ となる) 最小の $k$ を二分探索で求める．
      • このような $k$ が存在しない場合には，
        • $B$ には，$a_i$ を加える．
        • $J$ には，$i$ を加える．
        • $k := m + 1$ とする．($B = ()$ の場合には，$m = -1$ と考えて，$k := 0$)
      • 存在する場合には，
        • $b_k$ を $a_i$ で置き換える．
        • $j_k$ を $i$ で置き換える．
    • $c_i$ については，
      • $k > 0$ の場合には，$c_i := j_{k - 1}$ とする．
      • $k = 0$ の場合には，$c_i := -1$ とする．
  • 最終的に $B = (b_1, \dots, b_m)$，$J = (j_1, \dots, j_m)$ が得られたとする． 1 つの LIS が，次の手順で求められる．
    • 求める LIS の末項は，$b_m$ すなわち $a_{j_m}$ である．
    • $a_{j}$ が LIS の項である時，$c_j > 0$ なら，その一つ前の項は $a_{c_j}$ である．$c_j = -1$ ならそれが初項である．

4. 適用可能な問題