最長増加部分列

最長増加部分列（Longest Increasing Subsequence, LIS）問題は、与えられた数列から部分列を選び出す際に、選んだ要素が昇順になるという制約のもとで、その長さを最大化する組合せ最適化問題である。この問題は動的計画法の古典的な例題としてだけでなく、ソーティングネットワークの設計、最適化理論、計算生物学における配列解析など、幅広い応用を持つ基礎的なアルゴリズム問題として位置づけられる。

部分列とは、元の数列から任意の要素を選び出し、元の順序を保ったまま並べたものを指す。数学的に厳密に定義すると、数列 $A = (a_{1}, a_{2}, . . ., a_{n})$ に対して、インデックスの増加列 $i_{1} < i_{2} < . . . < i_{k}$ が存在するとき、 $(a_{i_{1}}, a_{i_{2}}, . . ., a_{i_{k}})$ を $A$ の部分列と呼ぶ。この部分列が $a_{i_{1}} < a_{i_{2}} < . . . < a_{i_{k}}$ を満たすとき、これを増加部分列と呼び、そのような部分列の中で長さ $k$ が最大のものを最長増加部分列と定義する。

例えば、数列 $[10, 9, 2, 5, 3, 7, 101, 18]$ に対しては、 $[2, 3, 7, 18]$ や $[2, 5, 7, 101]$ などが増加部分列となり、最長のものは $[2, 3, 7, 101]$ で長さ4となる。この例からも分かるように、最長増加部分列は一意に定まるとは限らず、同じ長さを持つ複数の解が存在することがある。

問題の計算複雑性と理論的背景

最長増加部分列問題は、一般的な部分構造最適性を持つ問題の典型例である。ある位置までの最適解が、それより前の位置での最適解を利用して構成できるという性質は、動的計画法の適用を可能にする。この問題に対する素朴な全探索アプローチでは $O (2^{n})$ の計算量を要するが、動的計画法により $O (n^{2})$ に、さらに二分探索を組み合わせることで $O (n \log n)$ まで改善できることが知られている。

理論計算機科学の観点から見ると、最長増加部分列問題は比較ベースのアルゴリズムにおいて $Ω (n \log n)$ の下界を持つことが証明されている。これは、 $n$ 個の異なる要素の順列に対して、その最長増加部分列の長さを求めることが、要素間の順序関係を決定することと等価であり、比較ソートの下界と同じ議論が適用できるためである^[1]。

この下界の証明は、情報理論的な議論に基づいている。 $n$ 個の要素の順列は $n!$ 通り存在し、これらを区別するためには少なくとも $\log_{2} (n!) = Θ (n \log n)$ ビットの情報が必要である。比較ベースのアルゴリズムでは、各比較で得られる情報は高々1ビットであるため、最悪ケースでは $Ω (n \log n)$ 回の比較が必要となる。

動的計画法による基本解法

最長増加部分列問題に対する動的計画法の適用では、部分問題を「位置 $i$ で終わる最長増加部分列の長さ」として定義する。これを $d p [i]$ と表記すると、以下の漸化式が成立する：

d p [i] = max_{j < i, a_{j} < a_{i}} (d p [j] + 1)

初期条件は $d p [i] = 1$ （各要素それ自身が長さ1の増加部分列を成す）である。この定式化により、各位置 $i$ について、それより前のすべての位置 $j$ を調べ、 $a_{j} < a_{i}$ を満たす場合に $d p [j] + 1$ の最大値を求めることで、 $d p [i]$ を計算できる。

この基本的なアプローチの計算量は $O (n^{2})$ となる。外側のループが $n$ 回、内側のループが最大で $i - 1$ 回実行されるため、全体の計算量は $\sum_{i = 1}^{n} i = O (n^{2})$ となる。空間計算量は $d p$ 配列を保持するための $O (n)$ である。

実装上の重要な考慮点として、最長増加部分列の長さだけでなく、実際の部分列を復元する必要がある場合がある。この場合、各 $d p [i]$ を計算する際に、どの $j$ から遷移してきたかを記録する親配列 $p a r e n t [i]$ を保持する。最終的に $d p$ 配列の最大値を持つ位置から、 $p a r e n t$ 配列を逆向きにたどることで、最長増加部分列を復元できる。

cpp

// O(n^2) の基本的な実装（疑似コード）
vector<int> findLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> parent(n, -1);
    int maxLen = 1, maxIdx = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }
    
    // Reconstruct the LIS
    vector<int> lis;
    for (int i = maxIdx; i != -1; i = parent[i]) {
        lis.push_back(nums[i]);
    }
    reverse(lis.begin(), lis.end());
    return lis;
}

二分探索による最適化

$O (n \log n)$ の計算量を実現する最適化されたアルゴリズムは、動的計画法の状態管理を工夫することで実現される。このアルゴリズムの核心は、「長さ $k$ の増加部分列の末尾の最小値」を管理する配列 $t a i l$ を維持することにある。

具体的には、 $t a i l [k]$ を「長さ $k$ の増加部分列のうち、末尾の値が最小となるものの末尾の値」と定義する。この配列は常に昇順に保たれるという重要な性質を持つ。なぜなら、もし $t a i l [i] \geq t a i l [i + 1]$ となる場合、長さ $i + 1$ の増加部分列から最初の要素を除けば長さ $i$ の増加部分列が得られ、その末尾は $t a i l [i + 1]$ となるが、これは $t a i l [i]$ の定義（最小性）に矛盾するからである。

アルゴリズムの動作を具体例で説明する。数列 $[10, 9, 2, 5, 3, 7, 101, 18]$ に対する処理を追跡すると：

初期状態： $t a i l = []$
$10$ を処理： $t a i l = [10]$
$9$ を処理： $9 < 10$ なので $t a i l [0] = 9$ 、 $t a i l = [9]$
$2$ を処理： $2 < 9$ なので $t a i l [0] = 2$ 、 $t a i l = [2]$
$5$ を処理： $5 > 2$ なので追加、 $t a i l = [2, 5]$
$3$ を処理： $2 < 3 < 5$ なので $t a i l [1] = 3$ 、 $t a i l = [2, 3]$
$7$ を処理： $7 > 3$ なので追加、 $t a i l = [2, 3, 7]$
$101$ を処理： $101 > 7$ なので追加、 $t a i l = [2, 3, 7, 101]$
$18$ を処理： $7 < 18 < 101$ なので $t a i l [3] = 18$ 、 $t a i l = [2, 3, 7, 18]$

最終的に $t a i l$ の長さ4が最長増加部分列の長さとなる。

この最適化の正当性は、各ステップで「長さ $k$ の増加部分列の末尾の最小値」という不変条件が保たれることから導かれる。新しい要素 $x$ が来たとき、 $x$ より小さい最大の $t a i l [j]$ を見つければ、長さ $j + 1$ の増加部分列を作ることができる。もし $t a i l [j + 1] > x$ であれば、 $x$ を末尾とする長さ $j + 1$ の増加部分列の方が、将来の拡張可能性が高いため、 $t a i l [j + 1]$ を $x$ で更新する。

実装上の詳細と最適化技法

実際の実装では、いくつかの重要な最適化技法が存在する。まず、二分探索の実装において、C++のlower_boundやPythonのbisect_leftのような標準ライブラリ関数を使用することで、バグの混入を防ぎつつ効率的な実装が可能となる。これらの関数は、ソートされた配列に対して、指定された値以上の最小の要素の位置を $O (\log n)$ で返す。

メモリアクセスパターンの観点から見ると、 $t a i l$ 配列は頻繁に参照・更新されるため、キャッシュ効率が重要となる。配列のサイズが小さい間は線形探索の方が二分探索より高速な場合もあるため、実装によっては小さなサイズに対する特殊化を行うことがある。

cpp

// 効率的な実装例（概念的な疑似コード）
int lengthOfLIS(vector<int>& nums) {
    vector<int> tail;
    for (int x : nums) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x);
        } else {
            *it = x;
        }
    }
    return tail.size();
}

部分列の復元が必要な場合、 $O (n \log n)$ のアルゴリズムでは追加の工夫が必要となる。一つの方法は、各要素がどの長さの増加部分列の末尾となったかを記録し、後ろから逆順にたどることである。この場合、各要素に対して $(v a l u e, l e n g t h)$ のペアを保持し、最後に長さが最大のものから貪欲に選んでいく。

cpp

// 部分列復元を含む実装（疑似コード）
vector<int> findLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> tail;
    vector<int> length(n);
    
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tail.begin(), tail.end(), nums[i]);
        length[i] = it - tail.begin() + 1;
        if (it == tail.end()) {
            tail.push_back(nums[i]);
        } else {
            *it = nums[i];
        }
    }
    
    // Reconstruct LIS
    vector<int> lis;
    int maxLen = tail.size();
    int curLen = maxLen;
    
    for (int i = n - 1; i >= 0 && curLen > 0; i--) {
        if (length[i] == curLen) {
            if (lis.empty() || nums[i] < lis.back()) {
                lis.push_back(nums[i]);
                curLen--;
            }
        }
    }
    
    reverse(lis.begin(), lis.end());
    return lis;
}

変種問題と一般化

最長増加部分列問題には多くの変種が存在し、それぞれが独自の応用を持つ。最も直接的な変種は、狭義単調増加（ $a_{i} < a_{i + 1}$ ）ではなく広義単調増加（ $a_{i} \leq a_{i + 1}$ ）を許す問題である。この場合、二分探索でlower_boundの代わりにupper_boundを使用することで対応できる。

より複雑な変種として、重み付き最長増加部分列問題がある。これは各要素に重みが付いており、部分列の重みの和を最大化する問題である。この問題は、セグメント木や平衡二分探索木を用いて $O (n \log n)$ で解くことができる。基本的なアイデアは、各値 $v$ に対して「 $v$ で終わる増加部分列の最大重み」を管理し、新しい要素を処理する際に範囲最大値クエリを用いることである。

$k$ -LIS問題は、最長増加部分列ではなく、 $k$ 番目に長い増加部分列を求める問題である。この問題は、動的計画法の状態を拡張し、各位置で終わる長さごとの部分列の個数を管理することで解ける。ただし、計算量は $O (n^{2} k)$ となり、大きな $k$ に対しては実用的でない場合がある。

2次元や多次元への拡張も重要な研究対象である。2次元平面上の点列に対して、 $x$ 座標と $y$ 座標の両方が増加するような部分列を求める問題は、計算幾何学や画像処理において応用がある。この問題は、点を $x$ 座標でソートした後、 $y$ 座標に対して通常の最長増加部分列アルゴリズムを適用することで解ける。

実践的な設計指針とトレードオフ

実際のシステムで最長増加部分列アルゴリズムを実装する際には、いくつかの設計上のトレードオフを考慮する必要がある。まず、入力サイズと要求される性能のバランスである。 $n$ が小さい（例えば1000未満）場合、 $O (n^{2})$ の単純な動的計画法の方が、実装の簡潔性とデバッグの容易さから好ましい場合がある。

メモリ使用量も重要な考慮事項である。基本的な $O (n \log n)$ アルゴリズムは $O (n)$ の追加メモリを必要とするが、部分列の復元も含めると $O (n)$ の定数倍が大きくなる。ストリーミング環境や組み込みシステムでは、このメモリ使用量が制約となる場合がある。

並列化の観点から見ると、最長増加部分列問題は本質的に逐次的な性質を持つため、直接的な並列化は困難である。しかし、複数の独立した配列に対して最長増加部分列を求める場合や、分割統治法を用いた近似解法では、並列処理による高速化が可能である。特に、van Emde Boasの手法^[2]では、配列を $\sqrt{n}$ 個のブロックに分割し、各ブロック内での局所的な最長増加部分列を並列に計算することで、理論的には $O (n \log \log n)$ の並列時間計算量を達成できる。

数値精度の問題も実践では重要である。浮動小数点数の配列に対して最長増加部分列を求める場合、比較の際の丸め誤差を考慮する必要がある。一般的には、ある許容誤差 $ϵ$ を設定し、 $| a_{i} - a_{j} | < ϵ$ の場合は等しいとみなすなどの処理が必要となる。

応用分野と実例

最長増加部分列アルゴリズムは、理論的な興味を超えて、多くの実用的な応用を持つ。計算生物学においては、DNA配列やタンパク質配列の類似性評価に用いられる。特に、遺伝子の進化的関係を推定する際に、保存された配列の順序を見つけるために活用される。

金融工学の分野では、株価や為替レートの時系列データから、最長の上昇トレンドを抽出するために使用される。この応用では、単純な価格の増加だけでなく、収益率や変動率を考慮した変種が用いられることが多い。

ネットワークルーティングにおいては、パケットの到着順序の乱れを検出・修正するために最長増加部分列が利用される。TCPのような信頼性の高い通信プロトコルでは、パケットの再送制御において、正しい順序で到着したパケットの最長列を識別することが重要となる。

機械学習の前処理としても応用がある。時系列データの異常検出において、正常なトレンドからの逸脱を検出するために、最長増加部分列との差分を特徴量として使用する手法が提案されている。

アルゴリズムの拡張と最新の研究動向

最長増加部分列問題の研究は現在も活発に行われており、特に以下の方向での拡張が注目されている。まず、オンラインアルゴリズムとしての定式化である。要素が順次与えられる状況で、各時点での最長増加部分列を効率的に維持する問題は、データストリーム処理において重要である。Lopezら^[3]は、スライディングウィンドウ内での最長増加部分列を $O (\log n)$ の更新時間で維持するアルゴリズムを提案している。

分散環境での最長増加部分列計算も研究されている。MapReduceフレームワークやより一般的な分散計算モデルにおいて、通信量を最小化しながら正確な解を求めるアルゴリズムが提案されている^[4]。基本的なアプローチは、配列を複数の部分に分割し、各部分での局所的な最長増加部分列を計算した後、それらを統合するというものである。

近似アルゴリズムの研究も重要である。厳密な最長増加部分列ではなく、 $(1 - ϵ)$ 近似解を高速に求めるアルゴリズムが存在する。これらのアルゴリズムは、サンプリングやスケッチング技法を用いて、 $O (n / ϵ)$ や $O (n \log \log n)$ といった準線形時間での計算を可能にする。特に、Ailon and Chazelle^[5]のアルゴリズムは、期待値で $O (n \log \log n)$ の時間計算量を達成している。

機械学習との融合も興味深い研究方向である。与えられた配列の特性（例えば、ほぼソート済みか、ランダムか）を学習し、その特性に応じて最適なアルゴリズムを選択するアダプティブなアプローチが提案されている。これにより、平均的なケースでの性能を大幅に向上させることができる。

量子アルゴリズムの文脈では、最長増加部分列問題に対する量子スピードアップの可能性が研究されている。現時点では、比較ベースのモデルにおいて古典的な $O (n \log n)$ アルゴリズムを大幅に改善する量子アルゴリズムは知られていないが、特殊な入力分布に対しては量子優位性が示されている場合がある。

外部記憶アルゴリズムの研究も実用上重要である。入力配列がメインメモリに収まらない場合、ディスクアクセスを最小化しながら最長増加部分列を計算する必要がある。この問題に対しては、キャッシュ効率的なアルゴリズムや、I/O複雑性を考慮したアルゴリズムが提案されている。

最長増加部分列問題は、その単純な定義にもかかわらず、アルゴリズム設計の多くの重要な概念を含む豊かな問題である。動的計画法、二分探索、データ構造の活用、計算複雑性の解析など、計算機科学の基礎的な技法が凝縮されており、これらの技法の理解と応用は、より複雑な最適化問題に取り組む際の強力な基盤となる。実践的な実装においては、問題の制約、システムの特性、要求される性能のバランスを考慮し、適切なアルゴリズムとデータ構造を選択することが重要である。

Fredman, M. L. (1975). On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1), 29-35. ↩︎
van Emde Boas, P. (1977). Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3), 80-82. ↩︎
Lopez-Ortiz, A., & Salinger, A. (2012). Longest increasing subsequences in sliding windows. Theoretical Computer Science, 421, 68-77. ↩︎
Tiskin, A. (2015). Fast distance multiplication of unit-Monge matrices. Algorithmica, 71(4), 859-888. ↩︎
Ailon, N., & Chazelle, B. (2005). Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. SIAM Journal on Computing, 39(1), 302-322. ↩︎

最長増加部分列 ​

問題の計算複雑性と理論的背景 ​

動的計画法による基本解法 ​

二分探索による最適化 ​

実装上の詳細と最適化技法 ​

変種問題と一般化 ​

実践的な設計指針とトレードオフ ​

応用分野と実例 ​

アルゴリズムの拡張と最新の研究動向 ​