yes good point pointed by atul it works only for positive numbers in matrix for negative numbers we have to consider maximum continuous sum for that row starting with that element
On Tue, Jan 17, 2012 at 10:28 AM, atul anand <atul.87fri...@gmail.com>wrote: > @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 < > usrivastav...@gmail.com> 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 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. > -- *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 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.
