@priya : i dont knw , how you came up with these values ...!!! and aove code given is not a full code , it just a sketch of code to make you understand.Before moving further,i would like to clarify that innner K-loop is running kadane algo(full code is not written). so i cut short in this by discussing the idea behind it....
After finding cumulative sum of each column ..moving top to bottom , Suppose we get this :- 1 0 0 0 1 1 1 -2 1 2 2 -4 2 3 2 -3 now IDEA is start from last row. -- ( I-Loop is handling this ) negate values i each cell of first row from the each cell for last row -- ( j-Loop is handling this ) i.e 2-1 , 3-0 , 2-0, -3-0 ==> 1,3,2,-3 1,3,2,-3 ==> now run kadane algo on this last row only and update max ( K-loop is doing this) similarly , when we increment j i.e now we move to second row which j loop is handling. do the same :- 2-1,3-1, 2-1,-3-2 // ---> run kadane algo on this and update max. now when j loop ends , then we are moving to second last row and doing the same ...as we did with last row in above example. i hope now you get it.. On 10/9/12, Priya Dhingra <priya.dhingr...@gmail.com> wrote: > i dnt know how ur algo is handling the case like [c2 d2 ,c3 d3] or [c1 d1, > c2 d2 ,c3 d3] > > > as i run this loop it is considering the following matrices > > > > > > i=3 j=0 nd k=0 to 3 > [a2 a3 a4],[a2 b2,a3 b3,a4 b4].[a2 b2 c2,a3 b3 c3,a4 b4 c4],[a2 b2 c2 d2 > ,a3 b3 c3 d3,a4 b4 c4 d4] > > i=3 j=1 nd k=0 to 3 > [a3 a4], [a3 b3, a4 b4],[a3 b3 c3, a4 b4 c4 d4],[a3 b3 c3 d3 ,a4 b4 c4 d4] > > i=3 j=2 k =0 to 3 > [a4] [a4 b4] [a4 b4 c4] [a4 b4 c4 d4] > > i=2 j=0 k=0 to 3 > [a2 a3] [a2 b2,a3 b3],[a2 b2 c2,a3 b3 c3],[a2 b2 c2 d2 ,a3 b3 c3 d3] > > i=2 j=1 k=0 to 3 > [a2] [a3 b3] [a3 b3 c3] [a3 b3 c3 d3] > > i=1 j= k =0 to 3 > [a2] [a2 b2] [a2 b2 c2][a2 b2 c2 d2] > > > > On Mon, Oct 8, 2012 at 9:53 PM, atul anand <atul.87fri...@gmail.com> wrote: > >> @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. >> > > > > -- > Best Regards > Priya Dhingra > > -- > 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.
