在具有1和0的矩阵中查找所有1的最大尺寸子矩阵

Question

假设给你一个mXn位图,由一个数组M [1..m,1 .. n]表示,其数据全部为0或1.一个全部的块是M [i .. i0形式的子数组,每个位等于1的j .. j0]描述和分析一个有效的算法来找到M中具有最大面积的全一块

我正在尝试制作动态编程解决方案.但是我的递归算法在O(n ^ n)时间内运行,即使在记忆之后我也想不到将它降到O(n ^ 4)以下.有人可以帮我找到更有效的解决方案吗？

Answer 1

O(N)(元素数)解决方案:

A
1 1 0 0 1 0
0 1 1 1 1 1
1 1 1 1 1 0
0 0 1 1 0 0 

生成一个数组C,其中每个元素表示高于1的数字并包括它,直到第一个0.

C
1 1 0 0 1 0
0 2 1 1 2 1
1 3 2 2 3 0
0 0 3 3 0 0 

我们希望找到的行R,和左,右指标l,r最大化(r-l+1)*min(C[R][l..r]).这是一个在O(cols)时间内检查每一行的算法:

保持一堆对(h, i),在哪里C[R][i-1] < h ? C[R][i].在任何位置cur,我们应该h=min(C[R][i..cur])对(h, i)堆栈中的所有对.

对于每个元素:

• 如果 h_cur>h_top
• • 推(h, i).
• 其他:
• • 同时h_cur<h_top:
• • • 弹出堆栈的顶部.
• • • 检查它是否会成为新的最佳,即(i_cur-i_pop)*h_pop > best.
• • 如果 h_cur>h_top
• • • 推(h, i_lastpopped).

我们示例中第三行的执行示例:

  i =0      1      2      3      4      5
C[i]=1      3      2      2      3      0
                                 (3, 4)
 S=         (3, 1) (2, 1) (2, 1) (2, 1)
     (1, 0) (1, 0) (1, 0) (1, 0) (1, 0)    
     (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) 

i=0, C[i]=1推(1, 0).
i=1, C[i]=3推(3, 1).
i=2, C[i]=2)流行(3, 1).检查是否(2-1)*3=3是最好的.
        最后i弹出的是1,所以推(2, 1).
i=3, C[i]=2)h_cur=h_top什么都不做.
i=4, C[i]=3推(3, 4).
i=5, C[i]=0)流行(3, 4).检查是否(5-4)*3=3是最好的.
        流行 (2, 1).检查是否(5-1)*2=8是最好的.
        流行 (1, 0).检查是否(5-0)*1=5是最好的.
        结束.(好吧,我们应该在最后添加额外的术语C [cols] = 0以获得良好的衡量标准).

Answer 2

这是一个O(numCols*numLines^2)算法.让S[i][j] = sum of the first i elements of column j.

我将在这个例子中使用算法:

M
1 1 0 0 1 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 1 1 0 0 

我们有:

S
1 1 0 0 1 0
1 2 1 1 1 1
2 3 2 2 1 1 
2 3 3 3 1 1

现在考虑在一维数组中找到所有1的最大子数组的问题.这可以使用这个简单的算法来解决:

append 0 to the end of your array
max = 0, temp = 0
for i = 1 to array.size do
  if array[i] = 1 then
    ++temp
  else
    if temp > max then
      max = temp
    temp = 0

例如,如果你有这个1d数组:

1 2 3 4 5 6
1 1 0 1 1 1

你这样做:

首先附加一个0:

1 2 3 4 5 6 7
1 1 0 1 1 1 0

现在,请注意,无论何时击中a 0,您都知道连续序列的结束位置.因此,如果保持当前1的运行总数(temp变量),则可以max在达到零时将该总数与到目前为止的最大值(变量)进行比较,然后重置运行总计.这将为您提供变量中连续序列的最大长度max.

现在您可以使用此子算法来查找问题的解决方案.首先0在您的矩阵中添加一列.然后计算S.

然后:

max = 0
for i = 1 to M.numLines do
  for j = i to M.numLines do
    temp = 0
    for k = 1 to M.numCols do
      if S[j][k] - S[i-1][k] = j - i + 1 then
        temp += j - i + 1
      else
        if temp > max then
          max = temp
        temp = 0

基本上,对于子阵列的每个可能高度(有O(numLines^2)可能的高度),通过应用一维数组(in O(numCols))的算法,找到具有该高度的最大区域的高度.

考虑以下"图片":

   M
   1 1 0 0 1 0 0
i  0 1 1 1 0 1 0
j  1 1 1 1 0 0 0
   0 0 1 1 0 0 0

这意味着我们将高度j - i + 1固定.现在,让那些之间的矩阵的所有元素i,并j包含地:

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

请注意,这类似于一维问题.让我们总结一下列,看看我们得到了什么:

1 2 2 2 0 1 0

现在,问题被简化为一维情况,除了我们必须找到连续j - i + 1(2在这种情况下是)值的子序列.这意味着我们j - i + 1"窗口" 中的每一列必须满一列.我们可以使用S矩阵有效地检查这一点.

要了解其S工作原理,请再次考虑一维案例:let s[i] = sum of the first i elements of the vector a.然后子序列的总和是a[i..j]多少？它是所有元素的总和,包括所有元素a[j]的总和,减去所有元素的总和,包括a[i-1]含义s[j] - s[i-1].除了s每列都有一个后,2d的情况也是一样的.

我希望这很清楚,如果您有任何其他问题,请询问.

我不知道这是否符合您的需求,但我认为还有一种O(numLines*numCols)基于动态编程的算法.我还想不通,除了你所追求的子阵是正方形的情况.然而,有人可能会有更好的洞察力,所以再等一下.