发现全部为1的最大尺寸子矩阵中具有基质1的和0的 [英] Finding maximum size sub-matrix of all 1's in a matrix having 1's and 0's

问题描述

假设你将得到一个MXN的位图，由数组M [1..M，1 .. N]的项均为0或1。全1块的形式为一个子psented重新$ P $ M [我.. I0，J .. J0]中，每个位等于1，描述和分析一个有效的算法来寻找并购为全1块，最大面积

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

我试图做一个动态规划的解决方案。但我的递归算法运行在为O（n ^ n）的时间，甚至记忆化后，我无法想象把它向下跌破为O（n ^ 4）的。有人可以帮助我找到一个更有效的解决方案？

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?

推荐答案

这是O（N）（元素的数量）的解决方案：

An O(N) (number of elements) solution:

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 ，其中重$ P $每个元素psents 1秒以上，并包括它的号码，直到第一个0。

Generate an array C where each element represents the number of 1s above and including it, up until the first 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 最大化（R-L + 1）*分（C [R] [l..r]）。这是一种算法来检查在O（COLS）每行时间：

We want to find the row R, and left, right indices l , r that maximizes (r-l+1)*min(C[R][l..r]). Here is an algorithm to inspect each row in O(cols) time:

维护一叠对（H，I），其中 C [R] [I-1]; ^ h≤C [R] [I] 。在任何位置CUR，我们应该有 H =分钟（C [R] [i..cur]）所有对（H，I） 在堆栈中。

Maintain a stack of pairs (h, i), where C[R][i-1] < h ≤ C[R][i]. At any position cur, we should have h=min(C[R][i..cur]) for all pairs (h, i) on the stack.

对于每一个元素：

• 如果 h_cur＆GT; h_top
• • 按（H，I）。
  • If h_cur>h_top
  • • Push (h, i).
    • 在 h_cur＆LT; h_top ：
    • • 弹出堆栈的顶部。
      • • Pop the top of the stack.
        • • 检查是否会做出新的最好的，即（I_CUR-I_POP）* h_pop＆GT;最佳。
          • • Check whether it would make a new best, i.e. (i_cur-i_pop)*h_pop > best.
            • 如果 h_cur＆GT; h_top
            • • 按（H，i_lastpopped）。
              • • Push (h, i_lastpopped).

                这在执行在我们的例子中，第三排的一个例子：

                An example of this in execution for the third row in our example:

                  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 是一个新的最好的。照片  最后我杀出为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就结束好措施）。

                i=0, C[i]=1) Push (1, 0).
                i=1, C[i]=3) Push (3, 1).
                i=2, C[i]=2) Pop (3, 1). Check whether (2-1)*3=3 is a new best.
                        The last i popped was 1, so push (2, 1).
                i=3, C[i]=2) h_cur=h_top so do nothing.
                i=4, C[i]=3) Push (3, 4).
                i=5, C[i]=0) Pop (3, 4). Check whether (5-4)*3=3 is a new best.
                        Pop (2, 1). Check whether (5-1)*2=8 is a new best.
                        Pop (1, 0). Check whether (5-0)*1=5 is a new best.
                        End. (Okay, we should probably add an extra term C[cols]=0 on the end for good measure).

                这篇关于发现全部为1的最大尺寸子矩阵中具有基质1的和0的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！