@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 <dabbcomput...@gmail.com>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 <atul.87fri...@gmail.com>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 <ashg...@gmail.com> 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 <atul.87fri...@gmail.com>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
>>>> <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.
>>>>
>>>
>>> --
>>> 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.
>>>
>>
>> --
>> 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.
>>
>
>
>
> --
> AMRIT
>
>
> --
> 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.
>
--
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.
