c - 在给定的二进制数据中找到最大面积

Question

我在描述用于查找二进制数据的最大矩形区域的算法时遇到问题，其中 1 的出现频率是 0 的 k 倍。数据始终为 n^2 位，如下所示:

例如 n = 4 的数据如下:

1 0 1 0
0 0 1 1
0 1 1 1
1 1 0 1

k 的值可以是 1 .. j(k = 1 表示 0 和 1 的数量相等)。

对于上面的数据示例和 k = 1 的解决方案是:

1 0 1 0 <- 4 x '0' 和 4 x '1'
0 0 1 1
0 1 1 1
1 1 0 1

但在这个例子中:
1 1 1 0
0 1 0 0
0 0 0 0
0 1 1 1

解决方案是:
1 1 1 0
0 1 0 0
0 0 0 0
0 1 1 1

我尝试了一些蛮力算法，但对于 n > 20，它变得太慢了。你能告诉我应该如何解决这个问题吗？

---

正如 RBerteig 所建议的那样 - 这个问题也可以这样描述:“在给定的正方形位图中，通过一些任意过程将单元格设置为 1 或 0，找到最大的矩形区域，其中 1 和 0 以指定的比例出现， k。”

Answer 1

Bruteforce 在这里对于 n < 100 应该很好，如果实现得当:下面的解决方案具有 O(n^4) 时间和 O(n^2) 内存复杂度。 10^8 次操作在现代 PC 上应该远低于 1 秒(特别是考虑到每个操作都非常便宜:几乎没有加法和减法)。

一些观察

1. 有 O(n^4) 个子矩形需要考虑，每个子矩形都可以是一个解决方案。
2. 如果我们能在 O(1)(常数时间)内找到每个子矩形中 1 和 0 的数量，我们将在 O(n^4) 时间内解决问题。
3. 如果我们知道某个子矩形中 1 的数量，我们就可以找到零的数量(通过面积)。

因此，问题简化为以下内容:创建数据结构，允许在常数时间内找到每个子矩形中 1 的数量。

现在，假设我们有子矩形 [i0..i1]x[j0..j1]。即，它占据 i0 和 i1 之间的行以及 j0 和 j1 之间的列。并让 count_ones 成为计算子矩形中 1 的个数的函数。

这是主要的观察结果:

count_ones([i0..i1]x[j0..j1]) = count_ones([0..i1]x[0..j1]) - count_ones([0..i0 - 1]x[0..j1]) - count_ones([0..i1]x[0..j0 - 1]) + count_ones([0..i0 - 1]x[0..j0 - 1])

与实例相同的观察:

AAAABBB
AAAABBB
CCCCDDD
CCCCDDD
CCCCDDD
CCCCDDD

如果我们需要找到 D 子矩形 (3x4) 中 1 的个数，我们可以通过取整个矩形 (A + B + C + D) 中 1 的个数，减去 (A) 中 1 的个数来实现+ B) 矩形，减去 (A + C) 矩形中 1 的个数，并添加 (A) 矩形中 1 的个数。 (A + B + C + D) - (A + B) - (A + C) + (A) = D

因此，我们需要表 sums，对于每个 i 和 j 包含子矩形 [0 中 1 的数量。 .i][0..j].
您可以在 O(n^2) 中创建此表，但即使是直接填充它的方法(对于每个 i 和 j 迭代 [0 ..i][0..j] 区域)将是 O(n^4)。

有了这张表，

count_ones([i0..i1]x[j0..j1]) = sums[i1][j1] - sums[i0 - 1][j1] - sums[i1][j0 - 1] + sums[i0 - 1][j0 - 1]

因此，时间复杂度达到O(n^4)。