JavaScriptで指定した値以下となる最大の部分長方形の合計を求めるアルゴリズム

問題の概要

2次元配列（数値の行列）と目標値 num を引数として受け取るJavaScript関数を作成します。この関数の目的は、行列内に存在するすべての長方形領域の中から、合計値が num を超えない範囲で最も大きいものを見つけ出し、その合計値を返すことです。

つまり、「合計が目標値以下である長方形」の中で最大の合計を求めるという問題です。

入力例

const arr = [
    [1, 0, 1],
    [0, -2, 3]
];
const num = 2;

出力例

const output = 2;

出力の解説

この場合、条件を満たす最適な長方形は次の部分行列です。

[
    [0, 1],
    [-2, 3]
]

この長方形の合計は 0 + 1 + (-2) + 3 = 2 となり、目標値 2 ちょうどに一致します。これ以上大きな合計を持つ長方形は存在しないため、答えは 2 となります。

アルゴリズムの考え方

この問題を効率的に解くには、以下の2つのテクニックを組み合わせます。

• 行のペアごとの累積和： 上端の行 l と下端の行 r の組み合わせをすべて列挙し、その間の各行の列ごとの合計を配列 dp に蓄積していきます。これにより、2次元の問題を1次元の配列問題に変換できます。
• カダネのアルゴリズム（Kadane's Algorithm）： 変換された1次元配列に対して最大部分配列和を高速に求めます。もし最大値が目標値以下であれば、そのまま候補として採用できます。

カダネのアルゴリズムで得られた最大値が目標値を超えてしまった場合は、単純な全探索（O(cols²)）に切り替えて、目標値以下となる最大の区間和を探します。さらに、途中で合計がちょうど num に一致すれば、それ以上探す必要がないため即座に結果を返すことで処理を高速化しています。

実装コード

const arr = [
    [1, 0, 1],
    [0, -2, 3]
];
const num = 2;

const maxSum = (arr = [], num = 1) => {
    const rows = arr.length;
    const cols = arr[0].length;
    let maxSum = -Infinity;

    for(let l = 0; l < rows; l++) {
        // 各行ペアに対する列ごとの累積和
        const dp = Array(cols).fill(0);

        for(let r = l; r < rows; r++) {
            let sum = 0, max = -Infinity;

            for(let c = 0; c < cols; c++) {
                dp[c] += arr[r][c];
                if(sum < 0) sum = 0;
                sum += dp[c];
                max = Math.max(max, sum);
            }

            if(max <= num) {
                // カダネの結果がそのまま使える場合
                maxSum = Math.max(max, maxSum);
            } else {
                // 目標値を超えたため、区間和を全探索
                max = -Infinity;
                for(let c = 0; c < cols; c++) {
                    sum = 0;
                    for(let d = c; d < cols; d++) {
                        sum += dp[d];
                        if(sum <= num) max = Math.max(sum, max);
                    }
                }
                maxSum = Math.max(max, maxSum);
            }

            // 完全一致が見つかれば早期リターン
            if(maxSum === num) return num;
        }
    }
    return maxSum;
};

console.log(maxSum(arr, num));

実行結果

コンソールには次のように出力されます。

2

計算量について

時間計算量は O(rows² × cols²) です。ただし、多くの場合カダネのアルゴリズム（O(cols)）で処理が完結するため、実際の動作はかなり高速です。空間計算量は O(cols) で、累積和を保持する配列のみを追加で使用します。

まとめ

このアプローチのポイントは、2次元の長方形問題を「行のペアの固定 + 1次元の最大区間和問題」へと分解することです。負の数が含まれる行列でも正しく動作し、目標値との一致が見つかった時点で早期終了する工夫により、実用的なパフォーマンスを実現しています。