@ atul and saurabh Here is my code of what m trying to implement .
here starting at bottom right corner we try to come up moving row by row . in end b matrix contain's dimention of rectangle which can be formed from Aij in Bij (width,height) plz.. post what u make of it... can it be improved to work for all case's ?? #include<iostream> #include<conio.h> using namespace std; main() { int width=0,height=1; int a[6][6]={0,1,1,1,1,0, 0,0,0,1,1,0, 0,1,1,1,1,0, 0,1,1,0,0,0, 0,1,1,0,0,0, 0,0,0,0,0,0 }; int b[6][6][2]={0}; int i,j; for(i=0;i<6;i++) { b[5][i][width]=1; b[i][5][width]=1; b[5][i][height]=1; b[i][5][height]=1; } for(i=4;i>=0;i--) { for(j=4;j>=0;j--) { if(a[i][j]!=a[i+1][j] & a[i][j]!=a[i][j+1]) { b[i][j][width]=1; b[i][j][height]=1; } else if(a[i][j]==a[i][j+1] & a[i][j]!=a[i+1][j]) { b[i][j][width]=b[i][j+1][width]+1; b[i][j][height]=1; //printf("widht\n"); } else if(a[i][j]==a[i+1][j] & a[i][j]!=a[i][j+1]) { b[i][j][width]=1; b[i][j][height]=b[i+1][j][height]+1; // printf("height\n"); } else { b[i][j][width]=min(b[i+1][j][width],b[i][j+1][width]+1); b[i][j][height]=min(b[i+1][j][height]+1,b[i][j+1][height]); } } } for(i=0;i<6;i++) { for(j=0;j<6;j++) { printf("%d,%d ",b[i][j][width],b[i][j][height]); } printf("\n"); } getch(); } On Wed, Mar 14, 2012 at 8:59 PM, atul anand <atul.87fri...@gmail.com> wrote: > @Sourabh : here we are talking abt 2 different problems in this > post..which are little bit similar. > > 1) original question says find max subset of matix contaning '1' and '0' > > we knw recurrence to solve this problem , as posted above. > > 2) now your question is to find max subset of matrix which contain +ve or > -ve numbers , not necessarily only '1' or '0' > > so in my solution , you need to give some input to solve this problem .... > and that input is say matrix m[][]. > if you check my solution then in just modifies input matrix to find > solution , its space complexity is O(1). > > > > On Thu, Mar 15, 2012 at 12:26 AM, Sourabh Singh > <singhsourab...@gmail.com>wrote: > >> @atul >> >> 1) it won't work for large dimention's coz their is a limit to size of >> array we can declare on stack. >> ( which is typically 10^6 as far as i know :-) ). >> >> 2) the algo i m trying to find would work in linear time. while this one >> is more then O(n^2) >> fo rvery very large input this algo would be very very slow.. making >> it impractial.. >> >> ( it's like if u can find substring's in linear time then why use an >> O(n^2) algo ;-) ) >> >> NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit >> short on time to check implemention of your algo right now ) >> >> >> >> On Wed, Mar 14, 2012 at 9:07 AM, atul anand <atul.87fri...@gmail.com>wrote: >> >>> @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" <rahul23111...@gmail.com> 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 < >>>> singhsourab...@gmail.com> 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 < >>>>> 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. >>>>> >>>> >>>> -- >>>> 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.