JavaScriptで2次元配列の最長増加パスを求める方法

増加シーケンス（Increasing Sequence）とは

増加シーケンスとは、隣り合う要素を見たときに、後ろの要素が前の要素以上であるような数列のことです。つまり、各要素が直前の要素と等しいか、それより大きければ増加シーケンスとみなされます。

例えば、以下のような数列はすべて増加シーケンスです。

4, 6, 8, 9, 11, 14 は増加シーケンス
3, 3, 3, 3, 3, 3, 3 も増加シーケンス（要素が等しくてもよいため）

問題の概要

今回作成するのは、数値の2次元配列 arr を唯一の引数として受け取るJavaScript関数です。この関数は、配列内を「値が増加しながら進むパス」の中で最も長いものの長さを求めて返す必要があります。

ここでいう「パス」とは、上下左右の4方向にのみ移動できるものとします（斜め移動は不可）。また、移動先のセルの値は、必ず現在のセルの値よりも大きくなければなりません。

例として、次の入力を考えてみましょう。

const arr = [
    [4, 5, 6],
    [4, 3, 7],
    [3, 3, 2]
];

この場合の出力は次のようになります。

const output = 4;

出力の解説

この配列における最長の増加パスは「4 → 5 → 6 → 7」であり、その長さが4だからです。

実装例

この問題は、深さ優先探索（DFS）とバックトラッキング、さらにメモ化（動的計画法）を組み合わせることで効率的に解くことができます。コードは以下の通りです。

const arr = [
    [4, 5, 6],
    [4, 3, 7],
    [3, 3, 2]
];
const longestIncreasingPath = (arr = []) => {
    let longest = 0;
    let dp = Array(arr.length).fill(null).map(() =>
        Array(arr[0].length).fill(1));
    const backtracking = (row, col) => {
        if (dp[row][col] != 1) return dp[row][col];
        let dRow = [1, 0, -1, 0];
        let dCol = [0, 1, 0, -1];
        for (let i = 0; i < dRow.length; i++) {
            let nR = row + dRow[i], nC = col + dCol[i];
            if (nR >= 0 && nR < arr.length && nC >= 0 && nC < arr[0].length && arr[nR][nC] > arr[row][col]) {
                dp[row][col] = Math.max(dp[row][col], 1 + backtracking(nR, nC))
            };
        };
        return dp[row][col];
    }
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr[0].length; j++) {
            longest = Math.max(longest, backtracking(i, j));
        };
    };
    return longest;
};
console.log(longestIncreasingPath(arr));

コードの解説

• バックトラッキングDFS： 各セルを起点に上下左右へ再帰的に探索し、値が増加する方向だけを辿っていきます。
• 再帰関数の役割： backtracking(row, col) は、指定されたセルを出発点とした最長増加パスの長さを返します。
• メモ化による高速化： dp 配列に各セルの計算結果をキャッシュしています。dp[row][col] が初期値の1以外であれば、すでに計算済みのため即座にその値を返し、重複計算を防ぎます。
• 全セルを起点に探索： 最後に、すべてのセルを起点として最長パスを求め、その中の最大値を答えとして返しています。

計算量について

メモ化により各セルは一度しか計算されないため、時間計算量は O(m × n)、空間計算量も O(m × n) となります（m・n はそれぞれ行数・列数）。これにより、大きな配列でも現実的な時間で処理が可能です。

実行結果

上記のコードをコンソールで実行すると、次の出力が得られます。

4