这是一种基于@j_random_hacker在评论中建议的“直方图中的最大矩形”问题的解决方案：

[算法]的工作原理是从上到下迭代各行，对于解决此问题的每一行，“直方图”中的“条”由从当前行开始的所有零连续向上的零尾组成（一列的高度为0
（如果当前行中有1）。

输入矩阵mat可以是任意可迭代的，例如文件或网络流。一次只需要一行。

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