我々は$n$個の数を持つ配列$a$を与えられる．タスクは$a$において最も長く，厳密に増加する部分列を見つけることである．

正式には$$i_1 < i_2 < \dots < i_k,\a < a < \dots < a$$

この記事ではこの課題を解くための複数のアルゴリズムについて説明します。またこの課題に還元できる他の問題についても説明します。

動的計画法による $O(n^2)$ の解法

動的計画法は、非常に多くの問題を解くことができる非常に一般的な手法である。

まず、最も長く伸びる部分列の長さだけを探し、部分列そのものを復元する方法は後で学ぶことにする。

長さを求める

このタスクを達成するために、配列$d$を定義する。まず$d$、次に$d$というように、この配列を徐々に計算していく。この配列が計算された後、問題の答えは配列$d$の中の最大値になる。

そこで、現在のインデックスを$i$とする。すなわち、値$d$を計算したいのであって、過去の値$d, \dots, d$はすべて既知である。すると、次の二つの選択肢がある。

• $d = 1$：求められる部分列は要素$a$のみからなる。
• $d > 1$: 必要な部分列には、$a$の前に別の数がある。この数に注目しよう。このように、$d$は次の式で計算できます。「インデックス$j$を固定すると、2つの要素$a$と$a$で終わる最も長い増加部分列の長さは$d+1$である」これらの値$d$は全て既知なので、$$d = \max_{syubstack{j = 0 \dots i-1 } a < a} で直接計算することができます。 \left(d + 1right)$$

この2つのケースを組み合わせると、$d$の最終回答が得られる：

$d = \max_{substack{j = 0 \dots i-1 \ª a < a} (1, ╱max_{So_2571↩max}) \left(d + 1right)\right)$$

実装

上に述べたアルゴリズムの実装を示します。これは、増加する最長部分配列の長さを計算します。

int lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

部分配列を復元

これまで、部分配列の長さを求める方法だけを学び、部分配列自体を求める方法については、学習していません。

部分配列を復元できるようにするために、配列$d$と一緒に計算する補助配列$p$を追加で生成します。$p$は$i$で終わる最も長く増加する部分配列の最後の2番目の要素のインデックス$j$になります。言い換えれば、インデックス$p$は最高値$d$が得られたのと同じインデックス$j$になるのです。この補助配列$p$はある意味で祖先を指している。

そして、部分配列を導き出すには、最大値$d$のインデックス$i$から始めて、部分配列全体を導き出すまで、つまり$d=1$の要素に到達するまで祖先をたどればよい。

リストアの実装

前節のコードを少し変更しよう。d$と並んで配列$p$を計算し、その後に部分列を計算します。

便宜上、元々$p = -1$で先祖を割り当てていますが、$d = 1$の要素では先祖の値は$-1$のままで、この方が少し便利に部分列を復元できるようになるでしょう。

vector<int> lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1), p(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

部分配列を復元する別の方法

補助配列 $p$ を使わずに部分配列を復元することも可能です。単に $d$ の現在の値を再計算して、どのように最大値に達したかを見ることができます。

この方法は少しコードが長くなりますが、代わりにメモリを少し節約することになります。

動的計画法と二分探索による $O(n \log n)$ の解法

この問題をより速く解くために、 $O(n^2)$ で動く別の動的計画法を作り、後で $O(n \log n)$ に改良します。

ここでは動的計画法の配列 $d$ を使用することにします。このとき、長さ$i$の部分配列が終了する要素を$d$とし、そのような配列が複数ある場合は、最小の要素で終了するものを選ぶ。

最初は$d=-infty$、他の要素については$d= \infty$とする。

再び、最初に$a$、次に$a$と徐々に数を処理し、各ステップで配列$d$を最新に保つ。

$a$の全ての要素を処理した後、望ましい部分配列の長さは$d < \infty$で最大の$l$となる。

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

ここで二つの重要な観察を行う。

配列$d$は常にソートにされる。 また、$a$という要素は最大でも1つの値$d$しか更新しない。

したがって、配列$d$の中からこの要素を見つけるには、二項探索を使えば$O(ⅳlog n)$で可能である。実際には、配列$d$の中から$a$より厳密に大きい最初の数を探しているだけであり、この要素を上記の実装と同じ方法で更新しようとするものです。1つは$d$の要素のインデックス、もう1つは「祖先」の配列$p$を作成します。$p$は要素$i$で終わる最適な部分配列の前の要素のインデックスになります。

配列$a$を繰り返しながら、$d$の計算と同時にこの2つの配列を維持することは簡単です。857>

Solution in $O(n \log n)$ with data structures

上記の$O(n \log n)$で最長の増加部分列を計算する方法の代わりに、別の方法としていくつかの簡単なデータ構造を使ってこの問題を解くことができます。

最初の方法に戻り、$d$は$j < i$、$a < a$の値$d + 1$であることを思い出してください。

従って、$$t] = dのような配列$t$を追加定義すると、値$d$の計算問題は、配列$t$の接頭辞の最大値を求めることと等価です：$$d = \maxleft(t – 1] + 1ờ)$$

配列（変更する）の接頭辞の最大値を求める問題は多くの異なるデータ構造によって解決できる標準的な問題です。 さらに入力数$a$が特に大きい場合は、数を圧縮する（$0$から$n-1$に番号を変える）か、暗黙のセグメントツリーを使う（重要な木の枝だけを生成する）等の工夫が必要になる。この方法では、動的計画法の解のトリッキーな特性について考える必要がありませんし、このアプローチにより、問題を非常に簡単に一般化できます（下記参照）。

Longest non-decreasing subsequence

これは実はほぼ同じ問題で、部分配列に同一の数字を使うことが許されるようになっただけです。

Number of longest increasing subsequences

最初に述べた方法、$O(n^2)$版でもデータ構造を使った版でもどちらでも使えます。857>

$a$で終わる最長増加部分列を作る方法の数は、$d$が最大となる$j$で終わる最長増加部分列のすべての方法の総和である。このような$j$は複数存在しうるので、それらを全て合計する必要がある。

セグメントツリーを使用することで、このアプローチは$O(n \log n)$で実装することも可能である。

Smallest number of non-increasing subsequences covering a sequence

与えられた$n$個の数字$a$からなる配列に対して、各色が非増加部分列を形成するように最小の色数で数字を着色することである。

これを解くには、必要な色の最小数は最も長い増加する部分列の長さに等しいことに気づく。

証明： この2つの問題の双対性を証明する必要がある。

最も長く増加する部分列の長さを$x$、カバーを形成する非増加部分列の最小個数を$y$とすると、$x = y$であることを証明する必要がある。よって、$y \ge x$となる。

ここで、$y > x$が成り立たないことを矛盾から示す。$y > x$と仮定し、$y$非増加部分行の任意の最適集合を考える。この集合を次のように変形する。最初の部分列が2番目の部分列の前に始まり、最初の部分列が2番目以上の数で始まるような部分列が2つある限り、この開始数を解除して2番目の開始数にくっつける。有限回のステップの後、$y$個の部分列ができ、それらの開始番号は長さ$y$の増加する部分列を形成する。$y > x$と仮定したので、矛盾に達した。

したがって、$y = x$となる。

数列の復元： 数列を部分配列に分割するには、左から右へ進み、現在の番号または現在の番号と等しいかそれより小さい番号で終わる部分配列に貪欲に割り当てればよい。

練習問題

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces・・・
• Codeforces・・・
• Topcoder – AutoMarket
• Tomorist
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – “North-East”

.