@ ALL
finding square matrix is quite a standard question and nw an easy one as
everyone knows the reccussence atul has given.
but i wanted to find max rectangle..
i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but here is what i remember..
1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top left corner of max rectangle and
proceed further down .
can someone suggest how can be proceed further..
[ NOTE: problem occurs mainly when their are more than one rectangles which
can be formed from same point ]
plz.. don't suggest the histogram method it's just a dirty way of avoiding
to work on getting this DP right. :-)
On Mon, Mar 12, 2012 at 11:29 PM, atul anand <[email protected]>wrote:
> here is the recurrence for solving this
>
> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] )
> );
>
>
> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma <[email protected]>wrote:
>
>>
>> April 4, 2010
>>
>> Given a binary matrix, find out the maximum size square sub-matrix with
>> all 1s.
>>
>> For example, consider the below binary matrix.
>>
>> 0 1 1 0 1
>> 1 1 0 1 0
>> 0 1 1 1 0
>> 1 1 1 1 0
>> 1 1 1 1 1
>> 0 0 0 0 0
>>
>> The maximum square sub-matrix with all set bits is
>>
>> 1 1 1
>> 1 1 1
>> 1 1 1
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
