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.
