@rahul: i have alreday explained it in the provided link. @sourbh : why it would not work for large dimension On 14 Mar 2012 19:39, "rahul sharma" <[email protected]> wrote:
> @atul..plz tell me an example for square matrix...actually i faced it > first tym...it executes...but explain plz.. > > On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh > <[email protected]>wrote: > >> @atul >> >> Also the histogram algo and algo given by you can't work on very very big >> dimentions. say 10^5 x 10^5 matrix. >> but if we can find a DP then we just need to keep 2 row's at a time. :-) >> >> >> >> On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh >> <[email protected]>wrote: >> >>> @atul >>> >>> read it .. >>> >>> it's good but more or less like the histogram algo.. i wanted a DP. >>> approach.. >>> >>> here is some of wat i heard from a senior in colg.. >>> >>> 1. at every index we can keep 4 variable >>> >>> ht: height of max rectangle possible at index above current >>> wt width " " " " " >>> " " >>> hl:height of max rectangle possible at index left of current >>> wl: " " " " " >>> " " >>> >>> >>> now problem is which one to take for current... index >>> >>> >>> >>> On Tue, Mar 13, 2012 at 10:52 AM, atul anand <[email protected]>wrote: >>> >>>> @ Sourabh: check solution i have posted in below link >>>> >>>> >>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0 >>>> >>>> >>>> >>>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh < >>>> [email protected]> wrote: >>>> >>>>> @ 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. >>>>> >>>> >>>> -- >>>> 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. > -- 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.
