JavaScriptで2つの配列に共通する部分配列の最大長を求める方法

問題の概要

JavaScriptで、リテラル値からなる2つの配列 arr1 と arr2 を引数として受け取る関数を作成します。この関数は、両方の配列に共通して現れる部分配列（サブアレイ）の中で最も長いものの長さを返す必要があります。

ここでの「部分配列」とは、元の配列から要素を連続した形で取り出したものを指します。順序が連続していなければならない点に注意してください。

入力例

const arr1 = [1, 2, 3, 2, 1];
const arr2 = [3, 2, 1, 4, 7];

出力例

const output = 3;

解説

この場合、最大長となる共通の部分配列は [3, 2, 1] です。その長さは 3 となります。

アルゴリズム：動的計画法（DP）による解法

この問題は動的計画法（Dynamic Programming）を使うことで効率的に解くことができます。基本的な考え方は以下のとおりです。

• dp[i][j] を「arr1[i] から始まる部分配列」と「arr2[j] から始まる部分配列」の共通先頭部分の長さと定義します。
• arr1[i] と arr2[j] が一致する場合、dp[i][j] = dp[i+1][j+1] + 1 となります。
• 一致しない場合は dp[i][j] = 0 とします。
• DPテーブル全体の中で最大値が答えになります。

計算量は時間・空間ともに O(n × m)（n、m はそれぞれの配列の長さ）であり、総当たり的な O(n² × m) の素朴な解法よりも大幅に高速です。

実装コード

const arr1 = [1, 2, 3, 2, 1];
const arr2 = [3, 2, 1, 4, 7];

const maximumLength = (arr1 = [], arr2 = []) => {
    // DPテーブルの初期化（サイズ: (arr1.length + 1) × (arr2.length + 1)）
    const dp = new Array(arr1.length + 1)
        .fill(0)
        .map(() => new Array(arr2.length + 1).fill(0));

    // 後ろから前へ走査することで、dp[i+1][j+1] を参照可能にする
    for (let i = arr1.length - 1; i >= 0; i--) {
        for (let j = arr2.length - 1; j >= 0; j--) {
            if (arr1[i] === arr2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
            } else {
                dp[i][j] = 0;
            }
        }
    }

    // テーブル内の最大値を返す
    return dp.reduce((acc, items) => Math.max(acc, ...items), 0);
};

console.log(maximumLength(arr1, arr2));

実行結果

3

まとめ

本記事では、JavaScriptを用いて2つの配列に共通する部分配列の最大長を求める方法を紹介しました。ポイントは次の3つです。

• 問題を「後ろから一致する長さ」として定式化すると、動的計画法で自然に解ける。
• 配列を逆順に走査することで、既に計算済みの dp[i+1][j+1] を利用できる。
• 最後にDPテーブル全体から最大値を取り出せば答えが得られる。

同様の手法は、文字列の最長共通部分文字列（Longest Common Substring）問題にもそのまま応用できます。ぜひ他の入力パターンでも試してみてください。