C++で最長増加部分列（LIS）を求めるプログラムの解説と実装例

最長増加部分列（Longest Increasing Subsequence：LIS）とは、数列の中から一部の要素を取り出して作った部分列のうち、各要素が直前の要素よりも常に大きくなるような列のことです。

本記事では、整数の集合が与えられたときに、その最長増加部分列の長さを動的計画法（DP）を用いて求める方法を解説します。

問題の例

入力：整数の集合 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
出力：最長増加部分列の長さ → 6
該当する部分列は 0, 2, 6, 9, 13, 15

アルゴリズムの考え方

この問題は動的計画法を使って効率よく解くことができます。基本的なアイデアは次のとおりです。

• 配列 length[i] を用意し、「i 番目の要素を末尾とする増加部分列の最大長」を記録します。
• 各要素 i について、それより前の要素 j（j < i）をすべて調べます。
• subarray[j] < subarray[i] かつ length[j] > length[i] を満たす場合、length[i] を length[j] で更新します。
• 最後に length[i]++ として、現在の要素自身を部分列に加えます。

longestSubSeq(subarray, n)

入力：部分配列とそのサイズ n

出力：最長増加部分列の長さ

Begin
    define array length of size n
    initially set 0 to all entries of length
        for i := 1 to n-1, do
            for j := 0 to i-1, do
                if subarray[j] < subarray[i] and length[j] > length[i], then
                    length[i] := length[j]
            done
        increase length[i] by 1
    done
    lis := 0
    for i := 0 to n-1, do
        lis := maximum of lis and length[i]
    done
    return lis
End

C++による実装コード

#include <iostream>
using namespace std;
int longestSubSeq(int subArr[], int n) {
    int length[n] = { 0 }; //すべての長さを0で初期化
    length[0] = 1;         //subArr[0]で終わる部分列の長さは1
    for (int i = 1; i < n; i++) {      //2番目以降の要素を順に処理
        for (int j = 0; j < i; j++) {  //subArr[j]で終わる部分列を確認
            if (subArr[j] < subArr[i] && length[j] > length[i])
                length[i] = length[j];
        }
        length[i]++; //現在の要素 subArr[i] を部分列に追加
    }
    int lis = 0;
    for (int i = 0; i<n; i++) //最長増加部分列の長さを求める
        lis = max(lis, length[i]);
    return lis;
}
int main() {
   int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
   int n = 16;
   cout << "Length of Longest Increasing Subsequence is: " << longestSubSeq(arr, n);
   return 0;
}

実行結果

Length of Longest Increasing Subsequence is: 6

計算量について

この実装では、すべての要素ペア（i, j）を比較するため、時間計算量は O(n²) となります。一方、空間計算量は補助配列 length の分だけ必要で、O(n) です。より大規模な入力に対しては、二分探索を組み合わせた O(n log n) の手法も知られていますが、理解しやすさという点ではこの DP アプローチが最適です。