@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 <singhsourab...@gmail.com>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 <atul.87fri...@gmail.com>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 <singhsourab...@gmail.com >> > 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 <atul.87fri...@gmail.com>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 <rahul23111...@gmail.com >>>> > 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 algogeeks@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com. >>>>> 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 algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> 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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
