C++で1のみを含む最大サイズの長方形部分行列を見つける方法

このチュートリアルでは、すべての要素が1である最大サイズの長方形部分行列(バイナリサブマトリックス)を見つけるプログラムについて解説します。

0と1のみで構成された2次元行列が与えられ、その中から「1だけで構成される最も大きな部分行列」の面積を求めるのが課題です。

アルゴリズムの考え方

この問題は、「ヒストグラムの中で最大の長方形を求める」という古典的な問題を応用することで効率的に解くことができます。手順は以下の通りです。

1. 1行目をそのままヒストグラムとみなし、スタックを使って最大長方形の面積を計算します。
2. 2行目以降では、現在のセルが1であれば、直前の行の同じ列の値に加算します。これにより、各列について「上方向へ連続して1が続いている高さ」が求まります。
3. 更新後の各行に対して同様に最大長方形の面積を計算し、これまでの最大値より大きければ答えを更新します。

この手法の計算量はO(R×C)であり、すべての長方形候補を総当たりで調べる方法に比べて大幅に高速です。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
// ヒストグラム内の最大長方形の面積を求める
int maxHist(int row[]) {
    stack<int> result;
    int top_val;
    int max_area = 0;
    int area = 0;
    int i = 0;
    while (i < C) {
        if (result.empty() || row[result.top()] <= row[i])
            result.push(i++);
        else {
            top_val = row[result.top()];
            result.pop();
            area = top_val * i;
        if (!result.empty())
        area = top_val * (i - result.top() - 1);
        max_area = max(area, max_area);
    }
}
while (!result.empty()) {
    top_val = row[result.top()];
    result.pop();
    area = top_val * i;
    if (!result.empty())
        area = top_val * (i - result.top() - 1);
        max_area = max(area, max_area);
    }
    return max_area;
}
 // 最大の部分行列の面積を返す
int maxRectangle(int A[][C]) {
    int result = maxHist(A[0]);
    for (int i = 1; i < R; i++) {
        for (int j = 0; j < C; j++)
        if (A[i][j])
        A[i][j] += A[i - 1][j];
        result = max(result, maxHist(A[i]));
    }
    return result;
}
int main() {
    int A[][C] = {
        { 0, 1, 1, 0 },{ 1, 1, 1, 1 },{ 1, 1, 1, 1 },{ 1, 1, 0, 0 },
    };
    cout << "Area of maximum rectangle is " <<
    maxRectangle(A);
    return 0;
}

実行結果

Area of maximum rectangle is 8

この入力例では、2行目と3行目にまたがる「縦2×横4」の長方形が最大となり、その面積は8になります。