longest_increasing_subsequence.html

<title>最長増加部分列 (LIS) について</title>
<h3>最長増加部分列問題 (LIS) について</h3>
<h4 class="shadow">最長増加部分列問題とは？</h4>
<p>最長増加部分列問題は、次のような有名問題です。</p>
<ul>
    <li>長さ $N$ の数列 $A_1, A_2, A_3, \dots, A_N$ が入力されるとき、そのうちいくつかの値を<b>順番を変えずに</b>取り出したときに、これが増加列となる中で最大の長さのものを求めなさい。</li>
    <li>数列 $b_1, b_2, b_3, \dots, b_k$ が「増加列」であるとは、$b_1 \leq b_2 \leq b_3 \leq \cdots \leq b_N$ が成り立つことである。</li>
</ul>
<p>例えば、次のような例があります。</p>
<ul>
    <li>$N = 7, A = (3, 5, 2, 6, 7, 1, 4)$ のとき、最長増加部分列は $(3, 5, 6, 7)$</li>
    <li>$N = 9, A = (3, 6, 9, 2, 5, 8, 1, 4, 7)$ のとき、最長増加部分列は $(3, 6, 9)$ や $(2, 5, 7)$、$(3, 5, 8)$ などたくさんあります。</li>
</ul>
<p>この記事では、最長増加部分列問題を通して、いろいろな問題と解法に触れていこうと思います。</p>
<br />
<h4 class="shadow">最長増加部分列の解法</h4>
<p>最長増加部分列は計算量 $O(N \log N)$ で解くことができます。しかし、それに至るまでにいろいろなアプローチがあるので順に説明していきます。</p>
<p>ここでは、最長増加部分列の長さを求める問題について考えます。</p>
<h5 class="shadow">解法 #1:  $2^N$ 通り全探索  -  計算量 $O \left(2^N \times N \right)$</h5>
<p>長さ $N$ の数列の「部分列」(数列のいくつかの値を順番を変えずに取り出した数列) は、"長さ $0$ の数列" を含めて $2^N$ 通りあります。</p>
<p>例えば、数列 $(2, 6, 1)$ の部分列は、$(), (2), (6), (1), (2, 6), (2, 1), (6, 1), (2, 6, 1)$ の $8 = 2^3$ 通りあります。</p>
<br />
<p>なぜ部分列は $2^N$ 通りあるのでしょうか？</p>
<p>数列のいくつかの値に丸を付けて、丸がつけられた数を左から読んだのが「部分列」というイメージで考えます。</p>
<p>それぞれの値は丸をつけられるかつけられないかの $2$ 通りなので、全部で $2 \times 2 \times \cdots \times 2 = 2^N$ 通りです。</p>
<br />
<p>どのように $2^N$ 通り全探索することができるのでしょうか？これには $2$ つの方法があります。</p>
<ul>
    <li>再帰を使った全探索</li>
    <li>$2$ 進数を使った全探索</li>
</ul>
<br />
<p>まず、再帰を使った全探索について説明します。実装すると、下のようなコードになります。</p>
<pre>
ans = 0
function solve(pos, seq):
    if pos == N:
        if seq が増加部分列:
            ans := max(ans, seq の長さ)
        return
    solve(pos + 1, seq)
    solve(pos + 1, seq の末尾に A[pos] を追加したもの)
</pre>
<p><code>solve(0, [])</code> を呼び出すと、計算が始まります。<code>pos</code> は「現在選ぶかどうか決めようとしている数が <code>A[pos]</code>」、<code>seq</code> は「現在の部分列」です。</p>
<p>その擬似コードの $4$～$6$ 行目は、選ぶ部分列が決まった場合の処理です。つまり、$4$～$6$ 行目を $2^N$ 回通ります。</p>
<p>7, 8 行目の意味は、<code>A[pos]</code> を選ぶか選ばないかで枝分かれする、という意味です。その第 $1$ 引数が <code>pos+1</code> になっているのは、<code>A[pos]</code> を選ぶかどうか決める次に <code>A[pos+1]</code> を選ぶかどうか決める、からである。</p>
<br />
<p>次に、$2$ 進数を利用した全探索について説明します。実装すると、下のようなコードになります。</p>
<pre>
ans = 0
for i = 0 to 2^N-1:
    seq = []
    for j = 0 to N-1:
        if (i を 2 進数で表したときの 2^j の位が 1 である):
            seq := (seq の末尾に A[j] を追加したもの)
    if seq が増加部分列:
        ans := max(ans, seq の長さ)
</pre>
<p>例えば、$N=3$ のとき。$0$～$7$ までの数を $2$ 進数で表すと <code>000, 001, 010, 011, 100, 101, 110, 111</code> となります。ここで「$1$」となっいる桁に対応する数に丸を付け、「$0$」となっている桁に対応する数には丸をつけない、という感じです。</p>
<p>すると、ありうる $2^N$ 通りすべての部分列 <code>seq</code> について調べることができます。</p>
<br />
<p>計算量は、両者ともに $2^N$ 通りすべてに対して増加部分列判定をするので、$O \left(2^N \times N \right)$ です。</p>
<p>初心者にとって再帰を理解するのは難しいと思うので、$2$ 進数を利用した全探索の方が分かりやすいでしょう。実装量は両方そんなに変わりません。</p>
<br />
<h5 class="shadow">解法 #2:  動的計画法 (DP) で計算量改善！  -  計算量 $O \left(N^2 \right)$</h5>
<p>この問題は、動的計画法 (DP) で解くことができます。最長増加部分列問題を DP を使って解く方法を説明します。</p>
<p>DP を理解していない人も、方法を読むことによって理解が進む良い問題の一例なので、ぜひ読んでみましょう。</p>
<br />
<p>左から順に丸を付けるかどうか決めることを考えます。$B_i$ を「最後に丸を付けた値が $A_i$ のときの、最長増加部分列の長さ」とします。</p>
<p>$B_1, B_2, B_3, \cdots, B_{i - 1}$ までの値が求まっているとき、なんと $B_i$ の値も求まってしまいます。</p>
<br />
<p>$B_i$ は、$j < i$ かつ $A_j \leq A_i$ であるような $j$ の中での $B_j$ の最大値 (ない場合は $0$) に、$1$ を足したものになります。</p>
<p>なぜなら、$B_j$ での答えとなる増加部分列の末尾に $A_i$ を追加したものが、最適になる数少ない候補だからです。</p>
<br />
<p>図で表すと、こんな感じの処理をすることになります。下図では、一番最後の $B_i$ の値を、今までに求めた $B_j \ (j < i)$ の値を使って求めています。矢印を見ると DP が何なのか分かりやすいかもしれません。</p>
<img src="https://i.ibb.co/jwW1tC3/image.png" alt="image" border="0" />
<br />
<p>実装は次のようになります。</p>
<pre>
for i = 0 to N-1:
    B[i] = 1  // 増加部分列が A[i] だけになるパターン
    for j = 0 to i-1:
        if A[j] < A[i]:
            B[i] := max(dp[i], dp[j] + 1) // 増加部分列を A[j] から A[i] に「つなげる」パターン
ans = 0
for i = 0 to N-1:
    ans := max(ans, B[i])
</pre>
<p>計算量は明らかに $O(N^2)$ で、先ほどの全探索の方法より改善しています。</p>
<p>このように、問題を「順番を決めて」前に求まった結果を利用して答えを求め、全探索の計算量を改善するみたいな方法を、「動的計画法」と言います。</p>
<br />