Can anyone explain maximum subarray 2D with example?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Can anyone explain maximum subarray 2D with example?

Post by lnr » Fri Apr 06, 2012 6:02 pm

Hi,

Can anyone describe/elaborate the maximum subarray 2D algorithm with example?

Here is a sample input output of a problem ( http://uva.onlinejudge.org/external/108/10827.html )
Input:

Code: Select all

2
5
1 -1 0 0 -4
2 3 -2 -3 2
4 1 -1 5 0
3 -2 1 -3 2
-3 2 4 1 -4
3
1 2 3
4 5 6
7 8 9
Output:

Code: Select all

15
45
I have searched in google about that algorithm, but could not understand their explaination.
http://alexeigor.wikidot.com/kadane
http://input-output.org/2010/01/27/maxi ... lem--in-2d
http://discuss.joelonsoftware.com/defau ... 1.784947.1
http://en.wikipedia.org/wiki/Maximum_subarray_problem

It will be nice if someone can provide step by step method with example.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Can anyone explain maximum subarray 2D with example?

Post by brianfry713 » Mon Apr 09, 2012 11:29 pm

http://acm.uva.es/board/viewtopic.php?t=7699

Also look at problem 108.

One way to solve 10827 is to duplicate the N*N matrix into a 2N*2N matrix and that takes care of the wraparound. So the first sample input would become:
1 -1 0 0 -4 1 -1 0 0 -4
2 3 -2 -3 2 2 3 -2 -3 2
4 1 -1 5 0 4 1 -1 5 0
3 -2 1 -3 2 3 -2 1 -3 2
-3 2 4 1 -4 -3 2 4 1 -4
1 -1 0 0 -4 1 -1 0 0 -4
2 3 -2 -3 2 2 3 -2 -3 2
4 1 -1 5 0 4 1 -1 5 0
3 -2 1 -3 2 3 -2 1 -3 2
-3 2 4 1 -4 -3 2 4 1 -4
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Algorithms”