what about taking sum of the boundaries of the rectangle and omiting the boundary with least sum and including the rest of rectangle in the sub-set?
On Mon, Jan 16, 2012 at 8:51 PM, atul anand <atul.87fri...@gmail.com> 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 <ashg...@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 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. > -- Umer -- 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.
