2次元行列で合計が最大になる長方形領域を求めるアルゴリズム

整数値で構成される2次元行列が与えられたとき、要素の合計が最大になる長方形（場合によっては正方形）の部分行列を見つける必要があります。

このアルゴリズムの基本的な考え方は、まず左右の列を固定し、各行ごとに左端の列から右端の列までの要素の合計を計算して一時的な配列に保存することです。その後、この一時配列に対してKadane（カダネ）のアルゴリズムを適用して最大合計の部分配列、すなわち上端と下端の行番号を特定します。これにより、合計が最大となる長方形全体が確定します。

入力と出力

入力：
整数の行列。
 1  2 -1 -4 -20
-8 -3  4  2  1
 3  8 10  1  3
-4 -1  1  7 -6

出力：
部分行列の左上と右下の座標、および部分行列の合計値。
(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29

アルゴリズム

kadaneAlgorithm(array, start, end, n)

入力：各行の合計を保持する配列、開始点と終了点、要素数。

出力：最大合計となる範囲の開始位置と終了位置を求めます。

Begin
    sum := 0 and maxSum := - ∞
    end := -1
    tempStart := 0

    for each element i in the array, do
       sum := sum + array[i]
       if sum < 0, then
          sum := 0
          tempStart := i + 1
       else if sum > maxSum, then
          maxSum := sum
          start := tempStart
          end := i
    done

    if end ≠ -1, then
       return maxSum
    maxSum := array[0], start := 0 and end := 0

    for each element i from 1 to n of array, do
       if array[i] > maxSum, then
          maxSum := array[i]
          start := i and end := i
    done

    return maxSum
End

maxSumRect(Matrix)

入力：与えられた行列。

出力：最大合計となる長方形の情報。

Begin
    maxSum := - ∞
    define temp array, whose size is same as row of matrix

    for left := 0 to number of columns in the Matrix, do
       till temp array with 0s
       for right := left to column of matrix -1, do
          for each row i, do
             temp[i] := matrix[i, right]
          done

          sum := kadaneAlgorithm(temp, start, end, number of rows)
             if sum > maxSum, then
                maxSum := sum
                endLeft := left
                endRight := right
                endTop := start
                endBottom := end
       done
    done

    display top left and bottom right corner and the maxSum
End

実装例

以下はC++による実装例です。

#include<iostream>
#define ROW 4
#define COL 5
using namespace std;

int M[ROW][COL] = {
    {1, 2, -1, -4, -20},
    {-8, -3, 4, 2, 1},
    {3, 8, 10, 1, 3},
    {-4, -1, 1, 7, -6}
 };

int kadaneAlgo(int arr[], int &start, int &end, int n) {    // 最大合計と開始・終了位置を求める
    int sum = 0, maxSum = INT_MIN;

    end = -1;    // 最初はどの位置も選択されていない

    int tempStart = 0;    // 0から開始

    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum < 0) {
            sum = 0;
            tempStart = i+1;
        }else if (sum > maxSum) {    // 最大合計を更新し、開始・終了インデックスを記録
            maxSum = sum;
            start = tempStart;
            end = i;
        }
    }

    if (end != -1)
        return maxSum;
    // 配列内のすべての要素が負の場合
    maxSum = arr[0];
    start = end = 0;

    // 配列内の最大要素を探す
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxSum) {
            maxSum = arr[i];
            start = end = i;
        }
    }
    return maxSum;
}

void maxSumRect() {
    int maxSum = INT_MIN, endLeft, endRight, endTop, endBottom;

    int left, right;
    int temp[ROW], sum, start, end;

    for (left = 0; left < COL; left++) {
        for(int i = 0; i<ROW; i++)// tempは最初、すべて0で初期化
            temp[i] = 0;

        for (right = left; right < COL; ++right) {
            for (int i = 0; i < ROW; ++i)    // 各行ごとに右端の列の値を加算
                temp[i] += M[i][right];
            sum = kadaneAlgo(temp, start, end, ROW);    // (top, left)～(bottom, right)の長方形の合計を求める

            if (sum > maxSum) {    // 合計の最大値を更新し、四隅の座標を記録
                maxSum = sum;
                endLeft = left;
                endRight = right;
                endTop = start;
                endBottom = end;
            }
        }
    }

    cout << "(Top, Left) ("<<endTop<<", "<<endLeft<<")"<<endl;
    cout << "(Bottom, Right) ("<<endBottom<<", "<<endRight<<")"<<endl;
    cout << "The max sum is: "<< maxSum;
}

int main() {
    maxSumRect();
}

出力結果

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

計算量

列のペアの組み合わせは O(C²) 通りあり、各ペアに対してKadaneのアルゴリズムを行数Rに対して適用するため O(R) の計算が必要です。したがって全体の時間計算量は O(R × C²) となります。これは、すべての長方形を素朴に列挙して合計を求める方法（O(R² × C²）よりも大幅に効率的です。

また、配列内のすべての要素が負数である場合でも、Kadaneのアルゴリズム後半の処理によって最大の単一要素が正しく返されるため、このコードはあらゆる入力に対応できます。