Given a 2D matrix find the maximum submatrix sum in it. The matrix is containing positive and negative integers. For example The maximum submatrix sum is 15 in the below given matrix.

Fig. 1.0

### maximum submatrix sum problem

The maximum submatrix sum problem can be consider as the extension of “Maximum contiguous sub array problem“. Kadane’s algorithm is used to find maximum sub array problem in 1 dimensional array (http://wikistack.com/maximum-subarray-problem/). We can extend the Kadane’s algorithm for 2D array to find maximum submatrix sum. Kindly see below figure for dynamic programming solution.

```#include<iostream>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;

#define n 4

int m[n][n] = { { 0, -2, -7, 0},
{ 9, 2, -6, 2},
{-4, 1, -4, 1},
{-1, 8, 0, -2}};

int sum[n];

int main ()
{
int max_ending_here, max_so_far;
int maximum = INT_MIN;

for (int i = 0; i < n; i++)
{
memset (sum, 0, n * sizeof (int));
for (int j = i; j < n; j++)
{

max_ending_here = 0;
max_so_far = INT_MIN;

for (int k = 0; k < n; k++)
{
sum[k] += m[j][k];
max_ending_here = max (0, max_ending_here + sum[k]);
max_so_far = max (max_so_far, max_ending_here);
}
maximum = max (maximum, max_so_far);
}
}
// print max sum
cout << maximum << endl;
return 0;
}
```

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=44