假设给定一个 mXn 位图，由数组 M[1..m,1..n] 表示，其条目全为 0 或 1。全为 1 的块是 M[i .. i0, 形式的子数组， j .. j0]，其中每个比特都等于 1。描述和分析一种有效的算法，以在 M 中找到最大面积的全一块
我正在尝试制作一个动态编程解决方案。但是我的递归算法在 O(n^n) 时间内运行，即使在记忆化之后，我也无法将其降低到 O(n^4) 以下。有人可以帮我找到更有效的解决方案吗？
问问题
425 次
1 回答
0
这只是一个想法，我不确定它是否有效。
将 A(i,j)(di,dj) 定义为从 (i,j) 到 (i+di,j+dj) 的全一个块，这意味着 M[x,y]=1 for i<=x <=i+di 和 j<=y<=j+dj。
如果不存在 A(i,j)(di+1,dj) 和 A(i,j)(di,dj+1)，则将A(i,j)(di,dj) 定义为最大块。
对于每个 (i,j)，我们可以构造最大块的列表，称为 L(i,j)。列表的最大长度为 min(m-i+1, n-j+1) <= min(m,n)。
L(i,j) 仅取决于 M[i,j]、L(i+1,j) 和 L(i,j+1)。我认为从 L(i+1,j) 和 L(i,j+1) 构造 L(i,j) 可以在线性时间内完成，这让我想起了排序列表的合并。使用 L(i,j)，在 L(i,j) 中找到 A(i,j)(di,dj) 的 max(di * dj)。这些值中的最大值指定了最大的全一块。
这种方法具有复杂性 n*m*min(m,n) ~= n^3 并且需要 min(m,n)^2 空间来存储所需的最后 2 行。
于 2010-11-10T12:08:36.060 回答