@amit : After understanding given example for 1D array ...you can consider each column as 1D array ...then i guess you will get it.
On Fri, Jan 20, 2012 at 2:32 PM, atul anand <[email protected]> wrote: > @amrit : inner most loop is running kadane algo :- > > i am not writing whole algo , just giving necessary information ... > you can google kadane algo... > > /********** > > for(k=0;k<col;k++) > { > sum_till_here+=mat[i][k] - *(mat[j][k])*; // here i am > excluding row = j and finding the max matrix sum. > // update max; > } > ***********/ > > and about this line : sum_till_here+=mat[i][k] - *(mat[j][k])*; > > here is the example considering 1D array :- > > consider arr[]={1,3,2,3}; > now find cumulative sum of this array. > you will get:- > c[]={1,4,6,9}; > > now if you do c[2] - c[0] = 5 // which sum of arr[1]+arr[2]; > c[3] - c[1] = 5 // which is sum of arr[2] + arr[3]; > > if you understood this then i guess you can understand the whole algo. > > NOTE : first you need to run *assumption 1)* and then *assumption > 2)*mentioned in my above post. > algo for assumption 1) is simple ....u just nedd to run kadane at each row > and update maxMat. > > let me know in case of doubt. > > > On Fri, Jan 20, 2012 at 11:24 AM, amrit harry <[email protected]>wrote: > >> @atul please explain above algo from 3 nested loops (last portion) i cant >> understand that part... >> please go further with the same example and solve it completly... >> Thanks. >> >> >> On Fri, Jan 20, 2012 at 10:33 AM, atul anand <[email protected]>wrote: >> >>> @Ashish: >>> >>> before moving on with solution to this problem , let understand the idea. >>> >>> consider arr[]={1,3,2,3}; >>> now find cumulative sum of this array. >>> you will get:- >>> c[]={1,4,6,9}; >>> >>> now take any index , say for example c[2] = 6 // c[2] is nothing but sum >>> of arra[0] + arr[1] + arrr[2] ; >>> similary for others. >>> >>> now if you do c[2] - c[0] = 5 // which sum of arr[1]+arr[2]; >>> c[3] - c[1] = 5 // which is sum of arr[2] + arr[3]; >>> >>> so basically anytime you do c[i] - c[j] = sum of arr[0 to i] - sum of >>> arr[0 to j]; >>> >>> >>> ----------------------------------------------------------------------------------------------------------------- >>> now lets understand solution to the given problem. >>> >>> given input:- >>> >>> >>> 1 0 0 0 >>> 0 1 1 -2 >>> 0 1 1 -2 >>> 1 1 0 1 >>> >>> find cumulative sum of each column , imagine given column as a simple 1D >>> array. >>> >>> we get, >>> >>> 1 0 0 0 >>> 1 1 1 -2 >>> 1 2 2 -4 >>> 2 3 2 -3 >>> >>> /************************** >>> now lets moving further , i would like to clear one more thing. >>> >>> 1 0 0 0 >>> 1 1 1 -2 >>> 1 2 2 -4 >>> 2 3 2 -3 >>> >>> add highlighted part you will get 1+2+2 = 5; >>> if you see the original matrix closely , 4 is the sum of highlighted >>> matrix below :- >>> >>> >>> 1 0 0 0 >>> 0 1 1 -2 >>> 0 1 1 -2 >>> 1 1 0 1 >>> >>> because each arr[i][j] contain sum of elements above it i.e sum of >>> arr[i][0 to j] >>> *********************************/ >>> >>> moving back to given problem :- >>> >>> *assupmtion 1 )* suppose maxMat exists anywhere *starting from* r=0 to >>> r= row-1; >>> run kadane algo for each row and updatemaxMat if( maxMat < newSum) >>> >>> this will take O(row * col ) >>> >>> *assumption 2)* suppose maxMat exists *between* anywhere between r=0 to >>> r=r-1; >>> >>> 1 0 0 0 >>> 1 1 1 -2 >>> 1 2 2 -4 >>> 2 3 2 -3 >>> >>> suppose max matrix exists anywhere b/w highlighted area above but as we >>> know each arr[i][j] given you sum starting from row=0; >>> >>> now we want to knw sum of elements above arr[i][j](in highlighted area) >>> excluding row[0][ j ] added to it. >>> >>> >>> for i=row-1 to 0 >>> for(j=0;j<i;j++) >>> // now run kadane algo... i am not writing full algo >>> for(k=0;k<col;k++) >>> { >>> sum_till_here+=mat[i][k] - *(mat[j][k])*; // here i am >>> excluding row = j and finding the max matrix sum. >>> // update max; >>> } >>> } >>> } >>> >>> O(row * row col ) >>> >>> hope you get it :) :) ....let me know in case of doubt. >>> >>> >>> On Thu, Jan 19, 2012 at 6:25 PM, Ashish Goel <[email protected]> wrote: >>> >>>> can you give the complete logic, not clear (: >>>> >>>> Best Regards >>>> Ashish Goel >>>> "Think positive and find fuel in failure" >>>> +919985813081 >>>> +919966006652 >>>> >>>> >>>> On Wed, Jan 18, 2012 at 10:05 AM, atul anand >>>> <[email protected]>wrote: >>>> >>>>> @sravanreddy001 : and kadane algo will be applied to each row. >>>>> >>>>> after finding cumulative sum. >>>>> at each row , apply kadane algo (here we are considering that matrix >>>>> could be anywhere starting from row=0 i.e it can be b/w row = 0 to row=1 >>>>> or >>>>> row =0 to row=2 , row=0 to row=3...etc ). >>>>> >>>>> find maxsum and update at each row. >>>>> >>>>> this will take O(row*col) >>>>> >>>>> now assume that maxMat can be b/w row=1 to row=2 , row=1 to row=3 , >>>>> row=2 to row=3 .....etc etc. >>>>> >>>>> for i=row-1 to 0 >>>>> for(j=0;j<i;j++) >>>>> // now run kadane algo... i am not writing full algo >>>>> for(k=0;k<col;k++) >>>>> { >>>>> sum_till_here+=mat[i][k] - (mat[j][k]); >>>>> // update max; >>>>> } >>>>> } >>>>> } >>>>> >>>>> this will take O(row*row*col) >>>>> >>>>> please let me know in case of any doubt or mistake. >>>>> >>>>> >>>>> On W ed, Jan 18, 2012 at 9:40 AM, atul anand >>>>> <[email protected]>wrote: >>>>> >>>>>> @sravanreddy001 : complexity would be : >>>>>> >>>>>> O(R^2 * C) >>>>>> where R and C are no. of rows and column respectively. >>>>>> >>>>>> >>>>>> On Wed, Jan 18, 2012 at 9:30 AM, sravanreddy001 < >>>>>> [email protected]> wrote: >>>>>> >>>>>>> Hi atul: >>>>>>> >>>>>>> Can u give the complexity for ur algorithm. >>>>>>> >>>>>>> I think of an O(m^2n^2) =~ O(n^4) algorithm, with constant space. >>>>>>> >>>>>>> The kadane's algo should be applied on a 2-d data right.. that takes >>>>>>> the complexity to order of 2. >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> 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/-/onh0-bxytOoJ. >>>>>>> >>>>>>> To post to this group, send email to [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]. >>>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> AMRIT >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
