83. 最長増加部分列（LIS）の長さを算出するアルゴリズムを丁寧に見る

数列 $A_n$ の増加部分列（Increasing Subsequence）は、「全ての $i \lt j$ で $A_i \lt A_j$ を満たす部分列」と定義されます。この部分列は、元の数列から非連続で取ることができ、順番を変えてはいけません。

たとえば、「 $3, 1, 4, 1, 5, 9, 2, 6$ 」という数列 $A_n$ の増加部分列の1つは、「 $A_2, A_5, A_6$ 」＝「 $1, 5, 9$ 」です。

増加部分列のうち、その長さが最長となるものを最長増加部分列（LIS: Longest Increasing Subsequence）といいます（以降 LIS と表記します）。競技プログラミングにおいては、LIS の長さを求める問題がよく出てきます。

たとえば、先ほどの数列 $A_n$ 、すなわち「 $3, 1, 4, 1, 5, 9, 2, 6$ 」の最長増加部分列の長さは $4$ になります（「 $A_2, A_3, A_5, A_8$ 」＝「 $1, 4, 5, 6$ 」が代表例です）。

LIS の長さを求めるアルゴリズムは、元の数列の長さを $N$ として $O(N \log N)$ のものが知られています。今回はそれについてまとめます。

LIS の長さを求めるアルゴリズム

長さ $n$ の増加部分列の最後の数を記録する配列 $L_n$ を準備します。この配列ですが、記録する「増加部分列の最後の数」についてできるだけ小さい値を優先するというルールを設けます。そのため、配列の各値は $\infty$ で初期化します。

f:id:ibako_piyo:20220314214049p:plain — 初期状態

数列 $A_n$ を先頭から順番に見て、その値で $L_n$ を更新していきます。このとき、 $L_n$ は（ $\infty$ を除いて）狭義単調増加となるように埋めていきます。

先ほどの例で具体的にどういう操作を行うのか見ていきます。まず、「 $A_1 = 3$ 」が $L_1$ に入ります。

f:id:ibako_piyo:20220314214632p:plain — $A_1 = 3$ を見たあとの状態

次に、 $A_2 = 1$ を見るのですが、 $L_n$ はできるだけ小さい値を優先するルールなので、 $L_1$ が更新されます。実際、この時点で長さ 2 の増加部分列は取れないので、状態に矛盾はありません。

f:id:ibako_piyo:20220314215015p:plain — $A_2 = 1$ を見たあとの状態

次に、 $A_3 = 4$ を見ます。これは $L_1$ の現在値より大きいので $L_2$ に入ります。実際、ここまでで長さ 2 の増加部分列を取ることができて、その最後の数の最小値は 4 になりますね。

f:id:ibako_piyo:20220314215203p:plain — $A_3 = 4$ を見たあとの状態

次に、 $A_4 = 1$ を見るのですが、 $L_n$ は狭義単調増加となるように埋めるルールです。そのため、適切な場所がないので $L_n$ は更新しません。

f:id:ibako_piyo:20220314215533p:plain — $A_4 = 1$ を見たあとの状態

…と、この調子で表を更新していくと、最終的に以下のような状態になります。実際手を動かして確かめてみてください。

f:id:ibako_piyo:20220314215716p:plain — $A_8 = 6$ を見たあとの状態

以上より、最長増加部分列の長さは 4 であることが分かりました。ちなみに、この表だけでは具体的な最長増加部分列を求められない点に注意してください。実際、表に残ったのは「 $1, 2, 5, 6$ 」ですが、このような長さ 4 の増加部分列は作れません。 $L_n$ は「長さ $n$ の増加部分列を作る際、最後の数となりうる最小値」を表すことを忘れないようにしましょう。

さて、このアルゴリズムの計算量を考察します。

単純に考えると、長さ $N$ の数列を見るとき、先頭から $N$ 文字を順番に確認して、その度に数値比較が $O(N)$ 回行われるので $O(N^2)$ です。

しかし、 $L_n$ は狭義単調増加を満たすように更新されるルールです。すなわち、更新すべき場所は二分探索で求められます。よって、数値比較は $O(\log N)$ 回行われることとなり、計算量は $O(N \log N)$ となります。

このアルゴリズムで LIS の長さが分かる理由のイメージ

ざっとアルゴリズムを見てきましたが、なんだかよく分からない、という人も多いと思います。そこで、なぜこのアルゴリズムで LIS の長さが分かるのか、イメージを掴むコツについて書きます。

ポイントは、やはり $L_n$ が最小値を優先し、狭義単調増加を保つ点にあります。DP的な考え方をするとイメージが掴みやすいです。

最小値を優先して $L_n$ を更新することの妥当性

$L_i$ の値が正しいとします。すなわち、「長さ $i$ の増加部分列を取得できて、その最後の数として $L_i$ を取れる」ことが正しいとします。

このとき、 $L_i \lt L_{i+1}$ を保つように、できるだけ小さな $L_{i+1}$ に更新しても良いことが分かります。 $L_i$ で終わる長さ $i$ の増加部分列の最後に $L_{i+1}$ を追加すると、長さ $(i+1)$ の増加部分列になるからです。

また、 $L_n$ を小さな値に更新するほど、より長い増加部分列を作れる可能性が高まります。なぜなら、小さな値を置いた方が後続に入れられる値の種類数が増えるからです。

よって、LIS を求めるためには最小値を優先して更新するのが良いです。

狭義単調増加を保つことの妥当性

では、 $L_n$ が狭義単調増加を保たないとどうなるでしょうか。仮に、 $L_i \ge L_j$ （ $i \lt j$ ）となる箇所があったとします。 $L_n$ の定義より、第 $j$ 項が $L_j$ となるような長さ $j$ の増加部分列を取れて、第 $i$ 項は $L_i$ 以上になります（第 $i$ 項までを見ると長さ $i$ の増加部分列となるため）。

ところが、 $L_i \ge L_j$ であるため、先ほど考えた長さ $j$ の増加部分列は増加部分列になっていません。

よって、背理法的に $L_n$ は狭義単調増加を保つ必要があります。

逆に、 $L_n$ が狭義単調増加を保つなら、 $L_i$ と $L_{i+1}$ が有効値であるようなすべての $i$ について $L_i \le B_i \lt L_{i+1} \le B_{i+1}$ となる $B_i = A_j$ と $B_{i+1} = A_k$ （ $j \lt k$ ）を取れることが保証されます。よって、 $B_{i}$ から増加部分列を構成できます。