@ 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.
