最長増加部分列問題 (LIS) について

最長増加部分列問題とは？

最長増加部分列問題は、次のような有名問題です。

• 長さ $N$ の数列 $A_1, A_2, A_3, \dots, A_N$ が入力されるとき、そのうちいくつかの値を順番を変えずに取り出したときに、これが増加列となる中で最大の長さのものを求めなさい。
• 数列 $b_1, b_2, b_3, \dots, b_k$ が「増加列」であるとは、$b_1 \leq b_2 \leq b_3 \leq \cdots \leq b_N$ が成り立つことである。

例えば、次のような例があります。

• $N = 7, A = (3, 5, 2, 6, 7, 1, 4)$ のとき、最長増加部分列は $(3, 5, 6, 7)$
• $N = 9, A = (3, 6, 9, 2, 5, 8, 1, 4, 7)$ のとき、最長増加部分列は $(3, 6, 9)$ や $(2, 5, 7)$、$(3, 5, 8)$ などたくさんあります。

この記事では、最長増加部分列問題を通して、いろいろな問題と解法に触れていこうと思います。

最長増加部分列の解法

最長増加部分列は計算量 $O(N \log N)$ で解くことができます。しかし、それに至るまでにいろいろなアプローチがあるので順に説明していきます。

ここでは、最長増加部分列の長さを求める問題について考えます。

解法 #1: $2^N$ 通り全探索 - 計算量 $O \left(2^N \times N \right)$

長さ $N$ の数列の「部分列」(数列のいくつかの値を順番を変えずに取り出した数列) は、"長さ $0$ の数列" を含めて $2^N$ 通りあります。

例えば、数列 $(2, 6, 1)$ の部分列は、$(), (2), (6), (1), (2, 6), (2, 1), (6, 1), (2, 6, 1)$ の $8 = 2^3$ 通りあります。

なぜ部分列は $2^N$ 通りあるのでしょうか？

数列のいくつかの値に丸を付けて、丸がつけられた数を左から読んだのが「部分列」というイメージで考えます。

それぞれの値は丸をつけられるかつけられないかの $2$ 通りなので、全部で $2 \times 2 \times \cdots \times 2 = 2^N$ 通りです。

どのように $2^N$ 通り全探索することができるのでしょうか？これには $2$ つの方法があります。

• 再帰を使った全探索
• $2$ 進数を使った全探索

まず、再帰を使った全探索について説明します。実装すると、下のようなコードになります。

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] を追加したもの)

solve(0, []) を呼び出すと、計算が始まります。pos は「現在選ぶかどうか決めようとしている数が A[pos]」、seq は「現在の部分列」です。

その擬似コードの $4$～$6$ 行目は、選ぶ部分列が決まった場合の処理です。つまり、$4$～$6$ 行目を $2^N$ 回通ります。

7, 8 行目の意味は、A[pos] を選ぶか選ばないかで枝分かれする、という意味です。その第 $1$ 引数が pos+1 になっているのは、A[pos] を選ぶかどうか決める次に A[pos+1] を選ぶかどうか決める、からである。

次に、$2$ 進数を利用した全探索について説明します。実装すると、下のようなコードになります。

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 の長さ)

例えば、$N=3$ のとき。$0$～$7$ までの数を $2$ 進数で表すと 000, 001, 010, 011, 100, 101, 110, 111 となります。ここで「$1$」となっいる桁に対応する数に丸を付け、「$0$」となっている桁に対応する数には丸をつけない、という感じです。

すると、ありうる $2^N$ 通りすべての部分列 seq について調べることができます。

計算量は、両者ともに $2^N$ 通りすべてに対して増加部分列判定をするので、$O \left(2^N \times N \right)$ です。

初心者にとって再帰を理解するのは難しいと思うので、$2$ 進数を利用した全探索の方が分かりやすいでしょう。実装量は両方そんなに変わりません。

解法 #2: 動的計画法 (DP) で計算量改善！ - 計算量 $O \left(N^2 \right)$

この問題は、動的計画法 (DP) で解くことができます。最長増加部分列問題を DP を使って解く方法を説明します。

DP を理解していない人も、方法を読むことによって理解が進む良い問題の一例なので、ぜひ読んでみましょう。

左から順に丸を付けるかどうか決めることを考えます。$B_i$ を「最後に丸を付けた値が $A_i$ のときの、最長増加部分列の長さ」とします。

$B_1, B_2, B_3, \cdots, B_{i - 1}$ までの値が求まっているとき、なんと $B_i$ の値も求まってしまいます。

$B_i$ は、$j < i$ かつ $A_j \leq A_i$ であるような $j$ の中での $B_j$ の最大値 (ない場合は $0$) に、$1$ を足したものになります。

なぜなら、$B_j$ での答えとなる増加部分列の末尾に $A_i$ を追加したものが、最適になる数少ない候補だからです。

図で表すと、こんな感じの処理をすることになります。下図では、一番最後の $B_i$ の値を、今までに求めた $B_j \ (j < i)$ の値を使って求めています。矢印を見ると DP が何なのか分かりやすいかもしれません。

実装は次のようになります。

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])

計算量は明らかに $O(N^2)$ で、先ほどの全探索の方法より改善しています。

このように、問題を「順番を決めて」前に求まった結果を利用して答えを求め、全探索の計算量を改善するみたいな方法を、「動的計画法」と言います。