@Priya : if first row is the max one , then it is actually boundary case which you can be handled easily,once you are done which above algo. please note that only first row need to checked if it max not every row , above algo is handling this . you can also modify given algo which will handle this boundary case. for rest of the cases it will work fine. It is handling cases like... c2d2 c3d3 etc... please try to understand idea behind the given algo ,let me know in case you have any further doubt.
On Mon, Oct 8, 2012 at 10:52 PM, Priya Dhingra <priya.dhingr...@gmail.com>wrote: > @atul if the largest matrix is [a1 b1 c1 d1 ] i mean if it is the > first row or if it is [c2 d2.i think then then ur code wont be giving the > right answer. > c3 d3] > > correct me if i'm wrong > > > On Monday, January 16, 2012 7:51:46 AM UTC-8, atul007 wrote: > >> >> find cumulative sum of each column. >> now for each arr[x][y] = sum of arr[i=0 to x] [j] ; >> >> a1 b1 c1 d1 >> a2 b2 c2 d2 >> a3 b3 c3 d3 >> a4 d4 c4 d4 >> >> now we have reduced this problem to find max-subarray . which can >> be efficiently calculated using kadane's algo for each row. >> >> NOTE: now suppose if row = 0 does not participate in calculating max sum >> matrix so u need to subtract a1 from a2,a3,a4 .... similarly for other >> element in row 1,2,3. >> >> now updated matrix considered i.e from (row =1 to row =3 ). for this >> updated matrix, >> each[x][y] is the sum of arr[i=1 to x] [j]. >> >> similarly do for other elements. >> >> On Mon, Jan 16, 2012 at 6:55 AM, Ashish Goel <ash...@gmail.com> wrote: >> >>> given a m*n matrix, find the subset rectangle with max sum (any other >>> rectangle taken would have lesser sum) >>> Best Regards >>> Ashish Goel >>> "Think positive and find fuel in failure" >>> +919985813081 >>> +919966006652 >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algo...@googlegroups.com. >>> To unsubscribe from this group, send email to algogeeks+...@** >>> googlegroups.com. >>> >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/4jFUDHYfBqUJ. > > 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.
