### Can anyone explain maximum subarray 2D with example?

Posted:

**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:
Output:
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.

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
```

Code: Select all

```
15
45
```

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.