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?
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
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
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:
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.
For each element:
h_cur>h_top
(h, i)
.h_cur<h_top
: (i_cur-i_pop)*h_pop > best
. h_cur>h_top
(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
) 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).