N×N の2値行列で0のみを含む最大の矩形を求めよ。

質問

NxNの2値行列（0か1しか含まない）があるとき、すべての0を含む最大の矩形を見つけるにはどうすればよいか？

例題です。

      I
    0 0 0 0 1 0
    0 0 1 0 0 1
II->0 0 0 0 0 0
    1 0 0 0 0 0
    0 0 0 0 0 1 <--IV
    0 0 1 0 0 0
            IV 

上記の例では、6×6の2値行列である。この場合の戻り値は、セル1:(2, 1)とセル2:(4, 4)となる。得られる部分行列は正方形でも長方形でもよい。 また、戻り値はすべての0の最大の部分行列の大きさ、この例では3×4とすることも可能である。

どのように解くのですか？

以下は ヒストグラムの最大矩形問題 に基づく解決策です。

[アルゴリズム] は、行を上から下へ反復することで動作します。 行を上から下へ、各行について を解く この問題 ここで ヒストグラムの棒グラフの構成は以下の通りです。 ゼロの切れ目のない上向きの軌跡からなる で構成されます（現在の行から始まる 列の高さが 0 であるのは、現在の行に 1 がある場合です。 を持つ場合、列の高さは 0 になります）。

入力行列 mat は，ファイルやネットワークストリームなど，任意の反復可能なものでよい．一度に利用できるのは1行のみです。

#!/usr/bin/env python
from collections import namedtuple
from operator import mul

Info = namedtuple('Info', 'start height')

def max_size(mat, value=0):
    """Find height, width of the largest rectangle containing all `value`'s."""
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_size = max_rectangle_size(hist)
    for row in it:
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        max_size = max(max_size, max_rectangle_size(hist), key=area)
    return max_size

def max_rectangle_size(histogram):
    """Find height, width of the largest rectangle that fits entirely under
    the histogram.
    """
    stack = []
    top = lambda: stack[-1]
    max_size = (0, 0) # height, width of the largest rectangle
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
            elif stack and height < top().height:
                max_size = max(max_size, (top().height, (pos - top().start)),
                               key=area)
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    for start, height in stack:
        max_size = max(max_size, (height, (pos - start)), key=area)    
    return max_size

def area(size):
    return reduce(mul, size)

解決策は O(N) であり、ここで N は行列の要素数です。これには O(ncols) の追加メモリが必要であり、ここで ncols は行列の列の数です。

テストを含む最新バージョンは https://gist.github.com/776423