C++で解く2次元行列の最大合計長方形 | 動的計画法(DP-27)

はじめに

本チュートリアルでは、2次元行列における最大合計長方形(Max Sum Rectangle)を求めるプログラムについて解説します。

具体的には、正数と負数が混在する2次元行列が与えられたとき、要素の合計が最大となる部分矩形(サブマトリクス)を効率よく見つけることが課題です。これは動的計画法(DP)の代表的な応用問題の一つであり、「DP-27」としても知られる定番テーマです。

アルゴリズムの考え方

この問題は、1次元配列の最大部分配列和を線形時間で求める有名なKadaneのアルゴリズムを2次元へ拡張することで解くことができます。基本的な手順は以下の通りです。

1. 左端の列 left を固定し、右端の列 right を left から右端まで順に移動させます。
2. 各ステップで、left〜right の範囲にある各行の要素を1次元配列 temp に累積加算し、2次元情報を1次元に圧縮します。
3. 圧縮した配列 temp に対してKadaneのアルゴリズムを適用し、最大合計とその上下の境界インデックスを取得します。
4. 得られた合計がこれまでの最大値を上回る場合は、矩形の四隅の座標と最大値を更新します。

この手法の時間計算量は O(cols² × rows) となり、すべての部分矩形を総当たりする O(rows² × cols²) のアプローチに比べて大幅に高速化できます。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
//最大合計を再帰的に返す
int kadane(int* arr, int* start,
int* finish, int n) {
    int sum = 0, maxSum = INT_MIN, i;
    *finish = -1;
    int local_start = 0;
    for (i = 0; i < n; ++i) {
        sum += arr[i];
        if (sum < 0) {
            sum = 0;
            local_start = i + 1;
        }
        else if (sum > maxSum) {
            maxSum = sum;
            *start = local_start;
            *finish = i;
        }
    }
    if (*finish != -1)
        return maxSum;
    maxSum = arr[0];
    *start = *finish = 0;
    //最大要素を探索
    for (i = 1; i < n; i++) {
        if (arr[i] > maxSum){
            maxSum = arr[i];
            *start = *finish = i;
        }
    }
    return maxSum;
}
void findMaxSum(int M[][COL]) {
    int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
    int left, right, i;
    int temp[ROW], sum, start, finish;
    for (left = 0; left < COL; ++left) {
        memset(temp, 0, sizeof(temp));
        for (right = left; right < COL; ++right) {
            for (i = 0; i < ROW; ++i)
                temp[i] += M[i][right];
            sum = kadane(temp, &start, &finish, ROW);
            if (sum > maxSum) {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }
    cout << "(Top, Left) (" << finalTop << ", " << finalLeft << ")" << endl;
    cout << "(Bottom, Right) (" << finalBottom << ", " << finalRight << ")" << endl;
    cout << "Max sum is: " << maxSum << endl;
}
int main() {
    int M[ROW][COL] = {
        {1, 2, -1, -4, -20},
        {-8, -3, 4, 2, 1},
        {3, 8, 10, 1, 3},
        {-4, -1, 1, 7, -6}
    };
    findMaxSum(M);
    return 0;
}

実行結果

(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
Max sum is: 29

出力の解説

この実行例では、行列内の (1,1)から(3,3) の位置にある3×3の部分矩形、すなわち以下の領域が最適解となります。

-3   4   2
 8  10   1
-1   1   7

この領域の要素を合計すると 29 となり、行列中で実現可能な部分矩形の合計の中で最大であることが分かります。

まとめ

2次元の最大合計長方形問題は、Kadaneのアルゴリズムと列方向の累積和を組み合わせることで効率的に解くことができます。競技プログラミングやコーディング面接でも頻出のテーマなので、ぜひ実装を通じて理解を深めておきましょう。