Can anyone explain maximum subarray 2D with example?

[lnr]

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]

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