コラム: 正方形と長方形の探求 (Maximal Square vs Rectangle)
BSQ課題では「最大の正方形」を探しますが、これに関連する有名な問題として「最大の長方形（Maximal Rectangle）」があります。 似ているようでいて、実は解法のアプローチが大きく異なるこの2つの問題を比較してみましょう。
1. ゴールの違い
| 問題 | ゴール | 制約 |
|---|---|---|
| Maximal Square | 最大の正方形を見つける | 縦と横の長さが同じでなければならない ($H = W$) |
| Maximal Rectangle | 最大の長方形を見つける | 縦と横の比率は自由 ($H \neq W$ も可) |
2. アプローチの違い
正方形の場合：動的計画法 (DP)
BSQで採用されている手法です。 「自分の左上、上、左のマスがどれだけ『正方形』を保っているか」という局所的な情報だけで、自分の位置で作れる最大正方形が決定できます。
c
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;この漸化式が成り立つのは、正方形の性質（縦横が等しい）のおかげです。「左上が3x3」「上が3x3」「左が3x3」なら、自分を含めれば「4x4」になれる、という単純な帰納法が成立します。
長方形の場合：ヒストグラム法 + スタック
長方形の場合、単純な近傍のDPでは解けません。左のマスの長方形が「横に細長い」もので、上のマスの長方形が「縦に細長い」ものだった場合、それらを統合した新しい長方形がどのような形になるか、単純な min/max では決まらないからです。
一般的に、Maximal Rectangle 問題は以下のステップで解かれます：
ヒストグラム変換: 各行を底辺としたとき、「上方向に連続して何個
1が続いているか」を計算し、棒グラフ（ヒストグラム）に見立てます。ヒストグラム内の最大長方形: 各行のヒストグラムについて、「ヒストグラム内に含まれる最大の長方形」を計算します。これには モノトニックスタック (Monotonic Stack) というデータ構造を使うことで、$O(N)$ で効率的に解くことができます。
まとめ
- 正方形探索 (BSQ) は、周囲との調和（min）を取るだけで済むため、シンプルで美しいDP解法が存在します。
- 長方形探索 は、自由度が高すぎるため、一度問題を「ヒストグラム」という別の形に変換し、スタックを用いて大域的な計算を行う必要があります。
同じような問題に見えても、制約がひとつ変わるだけで最適なアルゴリズムがガラリと変わるのは、アルゴリズムの面白いところですね。