C++で解く！すべてが1で構成される最大サイズの長方形バイナリ部分行列

問題概要

この問題では、0と1のみで構成された n × m の2次元行列 bin[][] が与えられます。私たちの課題は、すべての要素が1で構成される長方形の部分行列のうち、面積が最大になるものを見つけ、その最大面積を返すプログラムを作成することです。

具体例を使って問題を確認してみましょう。

入力

bin[][] = {
    {1, 0, 1, 1, 1}
    {0, 1, 1, 1, 1}
    {0, 0, 1, 1, 1}
    {1, 1, 1, 1, 1}
}

出力

12

説明

以下の部分行列（4行 × 3列）が最大の面積12を持ちます。

1, 1, 1
1, 1, 1
1, 1, 1
1, 1, 1

解法アプローチ

この問題を解くには、1のみで構成される最大の長方形部分行列を見つける必要があります。そのためには、「各行を処理した時点で、その行までに作れる長方形の最大面積」を順番に求めていきます。

まず、各列について現在の要素まで連続して並んでいる1の個数を高さとして累積的に計算します。これにより、各行を底辺とするヒストグラムが形成されます。次に、隣接する柱のうち同じ高さ以上のものを組み合わせて長方形を構成します。柱の高さがそれぞれ異なる場合は、最も低い柱の高さがその長方形の高さになります。

この「ヒストグラム内の最大長方形」の問題は、スタックを用いることで効率的に解くことができます。各行の処理が終わるたびに面積を計算し、それまでの最大値と比較することで、行列全体における最大面積を求められます。計算量は O(R × C) となり、総当たり方式よりも大幅に高速です。

サンプルプログラム

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 5

int calcAreaTillRow(int row[]) {
    stack<int> area1s;
    int tos;
    int maxArea = 0;
    int curArea = 0;
    int i = 0;
    while (i < C) {
        if (area1s.empty() || row[area1s.top()] <= row[i])
            area1s.push(i++);
        else {
            tos = row[area1s.top()];
            area1s.pop();
            curArea = tos * i;
            if (!area1s.empty())
                curArea = tos * (i - area1s.top() - 1);
            maxArea = max(curArea, maxArea);
        }
    }
    while (!area1s.empty()) {
        tos = row[area1s.top()];
        area1s.pop();
        curArea = tos * i;
        if (!area1s.empty())
            curArea = tos * (i - area1s.top() - 1);
        maxArea = max(curArea, maxArea);
    }
    return maxArea;
}

int calcmaxRecSubMat1(int bin[][C]) {
    int result = calcAreaTillRow(bin[0]);
    for (int i = 1; i < R; i++) {
        for (int j = 0; j < C; j++)
            if (bin[i][j])
                bin[i][j] += bin[i - 1][j];
        result = max(result, calcAreaTillRow(bin[i]));
    }
    return result;
}

int main() {
    int bin[][C] = {
        {1, 0, 1, 1, 1},
        {0, 1, 1, 1, 1},
        {0, 0, 1, 1, 1},
        {1, 1, 1, 1, 1}
    };
    cout << "The area of maximum size rectangle binary sub-matrix with all 1s is " << calcmaxRecSubMat1(bin);
    return 0;
}

実行結果

The area of maximum size rectangle binary sub-matrix with all 1s is 12

まとめ

本記事では、2次元バイナリ行列から1のみで構成される最大面積の長方形部分行列を求める方法を解説しました。各行をヒストグラムとして捉え、スタックを用いた最大長方形アルゴリズムを適用することで、O(R × C) の計算量で効率的に解くことができます。この手法は競技プログラミングや技術面接でも頻出のテクニックなので、ぜひ理解を深めておきましょう。