@UTKARSH : my approach is similar to yours written above. but does your algo taking into account the following conditions:-
1 0 0 0 0 1 1 -2 0 1 1 -2 1 1 0 1 here highlighted triangle is the max square . but i guess you are not considering this condition . correct me if i am wrong. On Tue, Jan 17, 2012 at 12:46 AM, UTKARSH SRIVASTAV <[email protected] > wrote: > > > I have an approach to solve this question my approach is basesd on given > question and it's solution so first of all understand this question and > it's solution > > > http://www.spoj.pl/problems/HISTOGRA/ > > http://www.ideone.com/lfORK > > I know I may not able to expplain properly but if you read it twice or > thrice with some feeling what's happening and how the two problem > solutions are linked to each other then you may get the answer. > > > Now for your matrix a[n][m] > do this first create another matrix s[n][m] > where s[i][j] = a[i][j] + a[i][j+1] + .. .+a[i][m-1] > s[i][j] = 0 if(a[i][j] = 0) > > now supposw for matrix a[4][4] > > 1 1 1 0 > 0 1 1 1 > 0 1 1 1 > 1 1 0 1 > > your s[n][m] will be > > 3 2 1 0 > 0 3 2 1 > 0 3 2 1 > 2 1 0 1 > > for(all columns 0 to 3 ) > { > consider rectangular bars are there with height s[i][j] where i will > be from 0 to n - 1 && j = column number which is fixed for each iteration. > then find solution using above algorithm and keep track of maximum area > } > then maximum area which you will get will give you solution > > > > > -- > *UTKARSH SRIVASTAV > CSE-3 > B-Tech 3rd Year > @MNNIT ALLAHABAD* > > > -- > 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.
