@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 <atul.87fri...@gmail.com>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
> <sravanreddy...@gmail.com>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 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.
