最長増加部分列（LIS）とは？動的計画法による求め方をC++で解説

最長増加部分列（Longest Increasing Subsequence、略称 LIS）とは、数列の中から一部の要素を選び出し、「選んだ要素が常にその直前の要素よりも大きい」という条件を満たす部分列のうち、最も長いものを指します。この記事では、整数の集合が与えられたときに、最長増加部分列の長さを求めるアルゴリズムを解説します。

入力と出力

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

アルゴリズム

使用する関数は 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

アルゴリズムの考え方

この手法は動的計画法（DP）に基づいています。補助配列 length の各要素 length[i] は、「i 番目の要素で終わる増加部分列の最大長」を表します。各位置 i に対して、それ以前のすべての位置 j を走査し、subArr[j] < subArr[i] を満たす中で最も長い部分列の長さに自分自身を加えて length[i] を更新します。最終的に length 配列の最大値が答えとなり、計算量は二重ループにより O(n²) です。

C++による実装例

#include <iostream>
using namespace std;

int longestSubSeq(int subArr[], int n) {
    int length[n] = { 0 };                     // すべてのlengthを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]++;                           // 自身の要素 arr[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

この例では、{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} という16個の整数から、0 → 2 → 6 → 9 → 13 → 15 という長さ6の増加部分列が最長であることが分かります。なお、より大規模なデータを扱う場合には、二分探索を組み合わせた O(n log n) の高速化手法も知られています。