algorithm - 在具有1和0的矩阵中找到所有1的最大大小子矩阵

假设给定一个mxn位图，由数组m[1..m，1..n]其条目都是0或1。all-one块是m[i..我，J..其中每一位等于1。描述并分析一种有效的求最大面积M的一个块的算法
我正在尝试做一个动态编程解决方案。但是我的递归算法在o（n^n）时间内运行，即使在记忆之后，我也无法将它降到o（n^4）以下。有人能帮我找到一个更有效的解决方案吗？

最佳答案

O（n）（元素数）溶液：

A
1 1 0 0 1 0
0 1 1 1 1 1
1 1 1 1 1 0
0 0 1 1 0 0

生成一个数组C，其中每个元素表示上面1的个数，包括它，直到第一个0。

C
1 1 0 0 1 0
0 2 1 1 2 1
1 3 2 2 3 0
0 0 3 3 0 0

我们想要找到行R，左边，右边的索引l，r最大化(r-l+1)*min(C[R][l..r])。下面是一个算法，可以在o（cols）时间内检查每一行：
在(h, i)中维护一个成对的堆栈。在任何位置cur，堆栈上的所有对都应该有C[R][i-1] < h ≤ C[R][i]。
对于每个元素：
如果h=min(C[R][i..cur])
按下(h, i)。
其他：
当h_cur>h_top时：
弹出堆栈的顶部。
检查它是否会产生新的最佳效果，即(h, i)。
如果h_cur<h_top
按下(i_cur-i_pop)*h_pop > best。
在我们的示例中，对第三行执行此操作的示例：

  i =0      1      2      3      4      5
C[i]=1      3      2      2      3      0
                                 (3, 4)
 S=         (3, 1) (2, 1) (2, 1) (2, 1)
     (1, 0) (1, 0) (1, 0) (1, 0) (1, 0)
     (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1)

h_cur>h_top）按(h, i_lastpopped)。
i=0, C[i]=1）按(1, 0)。
i=1, C[i]=3）弹出(3, 1)。检查i=2, C[i]=2是否是新的最佳值。
_
(3, 1)）(2-1)*3=3所以什么也不要做。
i）按(2, 1)。
i=3, C[i]=2）弹出h_cur=h_top。检查i=4, C[i]=3是否是新的最佳值。
__检查(3, 4)是否是新的最佳值。
__检查i=5, C[i]=0是否是新的最佳值。
_______结束。（好的，我们可能应该在末尾加上一个额外的c[cols]=0，以便更好地度量）。

关于algorithm - 在具有1和0的矩阵中找到所有1的最大大小子矩阵，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3806520/