algorithm - 查找完全由 1 组成的最大子数组（矩形）的区域的算法

Question

有一个二维二进制数组（0和的二维数组1），其中m行和n列；1给出一个有效的算法来找到完全由s组成的最大子数组（矩形）的区域。

public int findMaxRectangleArea(int[][] A,int m,int n);

有人可以帮我解决算法部分吗？

Answer 1

我会尝试这样的方法：

逐行从左到右迭代，直到找到0.

这0可能已经确定了1s 的两个矩形：

• 它上面的所有行
• 从左上角到左边的位置0

其中一个更大，记住它。

然后递归地下降到三个未知扇区（其中两个部分未知），它们可能仍然包含一个比您已经找到的更大的矩形：

确保您不再迭代已知行，这是多余的。

我相信这个解决方案最多可以查看每个字段两次（递归步骤的扇区重叠），所以它应该在 θ(x*y) 中运行。

Answer 2

这完全取决于您的最小数组维度有多大。如果它小于目标平台上的最大字长，则可以将数组制作成一维位图数组，并使用一系列滑动位掩码窗口来查找矩形。