矩阵中的连续全一块
假设给你一个 mXn 位图，由数组 M[1..m,1.. n] 表示，其条目 均为 0 或 1。全 1 块是 M[i .. i0, j .. j0] 形式的子数组，其中每一位都等于 1。描述并分析一种有效的算法来找到全 1 M 中具有最大面积的块
我正在尝试制定动态规划解决方案。但我的递归算法运行时间为 O(n^n)，即使在记忆之后，我也无法想到将其降低到 O(n^4) 以下。有人可以帮助我找到更有效的解决方案吗？
Suppose you are given an mXn bitmap, represented by an array M[1..m,1.. n] whose entries
are all 0 or 1. A all-one block is a subarray of the form M[i .. i0, j .. j0] in which every bit is equal to 1. Describe and analyze an efficient algorithm to find an all-one block in M with maximum area
I am trying to make a dynamic programming solution. But my recursive algorithm runs in O(n^n) time, and even after memoization I cannot think of bringing it down below O(n^4). Can someone help me find a more efficient solution?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这只是一个想法，我不确定它是否有效。
定义 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)(，则将 A(i,j)(di,dj) 定义为 max-block迪，DJ+1）。
对于每个 (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 行。
This is only an idea, and I'm not sure is it working.
Define A(i,j)(di,dj) to be all-one block from (i,j) to (i+di,j+dj), that means M[x,y]=1 for i<=x<=i+di and j<=y<=j+dj.
Define A(i,j)(di,dj) as max-block if there doesn't hold A(i,j)(di+1,dj) and A(i,j)(di,dj+1).
For each (i,j) we can contruct list, call it L(i,j), of max-blocks. Max length of list is min(m-i+1, n-j+1) <= min(m,n).
L(i,j) depends only on M[i,j], L(i+1,j) and L(i,j+1). I think that constructing L(i,j) from L(i+1,j) and L(i,j+1) can be done in linear time, it reminds me on merging of sorted lists.
With L(i,j), find max(di * dj) for A(i,j)(di,dj) in L(i,j). Maximal of these values specifies maximal all-one block.
This approach has complexity n*m*min(m,n) ~= n^3 and need min(m,n)^2 space for storing last 2 rows which are needed.