@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.
