@atul if the largest matrix is [a1 b1 c1 d1 ] i mean if it is the
first row or if it is [c2 d2.i think then then ur code wont be giving the
right answer.
c3 d3]
correct me if i'm wrong
On Monday, January 16, 2012 7:51:46 AM UTC-8, atul007 wrote:
>
>
> find cumulative sum of each column.
> now for each arr[x][y] = sum of arr[i=0 to x] [j] ;
>
> a1 b1 c1 d1
> a2 b2 c2 d2
> a3 b3 c3 d3
> a4 d4 c4 d4
>
> now we have reduced this problem to find max-subarray . which can
> be efficiently calculated using kadane's algo for each row.
>
> NOTE: now suppose if row = 0 does not participate in calculating max sum
> matrix so u need to subtract a1 from a2,a3,a4 .... similarly for other
> element in row 1,2,3.
>
> now updated matrix considered i.e from (row =1 to row =3 ). for this
> updated matrix,
> each[x][y] is the sum of arr[i=1 to x] [j].
>
> similarly do for other elements.
>
> On Mon, Jan 16, 2012 at 6:55 AM, Ashish Goel <[email protected]<javascript:>
> > wrote:
>
>> given a m*n matrix, find the subset rectangle with max sum (any other
>> rectangle taken would have lesser sum)
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>> --
>> 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]<javascript:>
>> .
>> To unsubscribe from this group, send email to
>> [email protected] <javascript:>.
>> 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/4jFUDHYfBqUJ.
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.
