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