【JavaScript】最長増加部分列（LIS）の総数を動的計画法で求める方法

問題

数値の配列 arr を第1引数（唯一の引数）として受け取るJavaScript関数を作成することを考えます。

この関数の目的は、その配列に含まれる最長増加部分列（連続・非連続を問わない）が何通り存在するかを求めることです。

たとえば、次のような入力が与えられた場合を考えてみましょう。

入力

const arr = [2, 4, 6, 5, 8];

出力

const output = 2;

出力の解説

この配列における最長の増加部分列は [2, 4, 5, 8] と [2, 4, 6, 8] の2通りです。どちらも長さは4であるため、答えは 2 となります。

アプローチ：動的計画法（DP）

この問題は、動的計画法を使うことで効率よく解けます。各インデックスに対して、次の2つの配列を用意します。

• distance[i] … インデックス i の要素で「終わる」最長増加部分列の長さ
• count[i] … インデックス i の要素で「終わる」最長増加部分列の個数

すべてのペア (i, j)（i < j）について、arr[j] > arr[i] を満たす場合は、arr[j] を arr[i] の末尾に連結できることを意味します。このとき、

• distance[j] がまだ更新されていない（または短い）場合 → distance[j] を distance[i] + 1 に更新し、count[j] を count[i] で置き換える
• distance[j] がすでに distance[i] + 1 と等しい場合 → 同じ長さの別ルートが見つかったので、count[j] に count[i] を加算する

最後に、最大長 max と同じ distance を持つすべてのインデックスについて count を合計すれば、それが答えになります。

コード例

実際のコードは以下の通りです。

const arr = [2, 4, 6, 5, 8];

const countSequence = (arr) => {
    // 各位置で終わる最長増加部分列の長さと個数を初期化
    const distance = new Array(arr.length).fill(1);
    const count = new Array(arr.length).fill(1);
    let max = 1;

    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] > arr[i]) {
                // より長い増加列が作れる場合
                if (distance[j] <= distance[i]) {
                    distance[j] = distance[i] + 1;
                    count[j] = count[i];
                    max = Math.max(distance[j], max);
                // 同じ長さの別ルートが見つかった場合
                } else if (distance[j] === distance[i] + 1) {
                    count[j] += count[i];
                }
            }
        }
    }

    // 最長の長さに到達できる経路の個数を合計
    return distance.reduce((acc, d, index) => {
        if (d === max) {
            acc += count[index];
        }
        return acc;
    }, 0);
};

console.log(countSequence(arr));

実行結果

2

計算量について

このアルゴリズムは二重ループを使用するため、時間計算量は O(n²) です。空間計算量は distance と count の2つの配列分となるため O(n) です。配列の要素数が数千程度までであれば十分実用的な速度で動作します。