@atul.ok i got it thanx a lot On Tue, Oct 9, 2012 at 10:08 AM, atul anand <atul.87fri...@gmail.com> wrote:
> @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. > > -- 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.
