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

Question

假设给出了一个mXn位图，由一个数组M [1..m，1..n]表示，其条目都是0或1 。全一块是M [i .. i0，j .. j0]形式的子数组，其中每一位等于1.描述和分析一个有效的算法以找到M中的全一块区域

我正在尝试制作动态编程解决方案。但我的递归算法在O（n^n）时间内运行，即使在记忆之后，我也无法想象将它放在O（n^4）之下。有人能帮我找到更有效的解决方案吗？

Answer 1

这是一个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 

现在考虑找所有的人的最大子数组的一维数组的问题。这可以通过使用这种简单的算法来解决：

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 

举例来说，如果你有这样的一维数组：

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 

现在，请注意，无论何时您点击0，您都知道在哪里连续的序列结束。因此，如果您保持当前数量的运行总数（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)可能高度），则发现通过应用算法为一维阵列，其具有高度的一个具有最大面积（在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的工作原理，请再次考虑一维情况：让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。

我希望这很清楚，如果您还有其他问题，请询问。

我不知道这是否适合您的需求，但我认为还有一个基于动态编程的算法。我还没有弄明白，除了你之后的子阵是正方形的情况。不过，有人可能会有更好的洞察力，所以请稍等一下。

Answer 2

的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+1)*min(C[R][l..r])的行R和左右索引l,r。这里是一个算法来检查每个行中的O（cols）时间：

保持一对堆栈(h, i)，其中C[R][i-1] < h ≤ C[R][i]。在任何位置，我们应该有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）Pop (3, 4)。检查(5-4)*3=3是否是最好的。
Pop (2, 1)。检查(5-1)*2=8是否是最好的。
Pop (1, 0)。检查(5-0)*1=5是否是最好的。
结束。 （好吧，我们可能应该在最后加上一个额外的C [cols] = 0来衡量）。

Answer 3

定义一个新的矩阵一个将存储在A [i，j]中的两个值：在i，j左上角的最大子矩阵的宽度和高度，填充矩阵从右下角开始，按行从下到上。你会发现四种情况： 当在[i，j] = 1处给出矩阵时执行这些情况：

情况1：原始矩阵中的右边或底部相邻元素都不等于当前值，即：在这种情况下，M [i，j]！= M [i + 1，j]和M [i，j]！= M [i，j + 1] j]为1x1

情况2：右边的相邻元素等于当前的元素，但底部的元素不同，A [i，j] .width的值为A [i + 1，j] A [i，j] .width = 1，A [i，j] .height = 1

情况3：底部的相邻元素相等但右边的元素不同，A [ i，j] .height = A [i，j + 1] .height + 1

壳体4：两个相邻数字的相等： 三个矩形被认为是：

1. A [I，J] .WIDTH = A [I，J + 1] .WIDTH + 1; A [I，J] .height = 1;

2. A [i，j] .height = A [i + 1，j] .height + 1;一个[I，J]。宽度= 1; A [i，j] .width = A [i + 1，j] .width + 1，A [i，j + 1] .width）和A [i，j] .height =分（A [I，J + 1] + 1，A [1 + 1，j]的）

在上述三种情况与最大面积的一个将被认为在这个位置来表示的矩形。

i，j左上角最大矩阵的大小为A [i，j] .width * A [i，j] .height因此您可以更新计算出的A的最大值[i，j]

底部行和最右边的列元素被视为分别向下和向右的邻居是不同的。

Answer 4

这是在C＃中的O（N）实现。

这个想法是使用动态编程来构建一个具有最大子矩阵大小（包括当前单元格本身）的累积矩阵。

public static int LargestSquareMatrixOfOne(int[,] original_mat) 
    { 
     int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)]; 
     AccumulatedMatrix[0, 0] = original_mat[0, 0]; 
     int biggestSize = 1; 
     for (int i = 0; i < original_mat.GetLength(0); i++) 
     { 
      for (int j = 0; j < original_mat.GetLength(1); j++) 
      { 
       if (i > 0 && j > 0) 
       { 
        if (original_mat[i, j] == 1) 
        { 
         AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1; 
         if (AccumulatedMatrix[i, j] > biggestSize) 
         { 
          biggestSize = AccumulatedMatrix[i, j]; 
         } 
        } 
        else 
        { 
         AccumulatedMatrix[i, j] = 0; 
        } 
       } 
       else if ((i > 0 && j == 0) || (j > 0 && i == 0)) 
       { 
        if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; } 
        else { AccumulatedMatrix[i, j] = 0; } 
       } 
      } 
     } 
     return biggestSize; 
    }