# maximum submatrix sum problem

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.

*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

## Leave a Reply