NxN bir ikili matris (sadece 0 ya da 1 içeren) verilen, nasıl 0 tüm büyük dikdörtgen içeren bulma konusunda gidebilir miyiz?

Örnek:

      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 

Yukarıdaki örneğin, bir 6×6 ikili matris. bu durumda dönüş değeri Cep 1:(2, 1) ve Cep 2:(4, 4) olacaktır. Alt matris elde edilen kare veya dikdörtgen. Dönüş değeri de en büyük alt-matris tüm bu örnekte 0, 3 × boyutu olabilir; 4.

İşte çözüm "Largest Rectangle in a Histogram" problem dayalı yorum @j_random_hacker tarafından önerilen:

[Algoritma] yineleme ile çalışır yukarıdan aşağıya satır, her satırda çözme this problem, "bar", "" içerir histogram yollar sıfır tüm kırılmamış Yukarı geçerli satırın başlangıç (bir sütun eğer 1 ise 0 yüksekliğe sahiptir satır geçerli).

mat matris giriş keyfi bir iterable örneğin, bir dosya veya bir ağ akışı olabilir. Sadece bir defada bir satır kullanılabilir olması için gereklidir.

#!/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)

Çözüm N bir matris elemanları sayısıdır O(N). ncols Bir matrisin sütun sayısı O(ncols) ek bellek gerektirir.

Testleri ile en son sürüm https://gist.github.com/776423