在给定 bool 数组中查找最大矩形区域的算法

Question

所以问题本身很简单，每次输入，给我一个宽度和高度，都不会超过200，然后是一串0和1代表二维平面。

像这样。

4 5
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1

目标是求右边的面积，面积为12，不用说，矩形只能由1组成。

我在写这篇文章的时候考虑过 flood-fill，但是它必须为数组中的每个 1 重新计算。最佳算法是什么？

Answer 1

类似于下面的问题:找到和最大的子矩阵。这可以通过 O(n^3) 算法来完成。我相信你可以在 stackoverflow 上找到它或在互联网上搜索。

对于这道题，可以把0换成-INF，然后应用上面的算法求出最大的矩形区域。