Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

#include
using namespace std;

#define MAX(a, b) (a>b ? a : b)
#define MIN(a, b) (a>b ? b : a)
int const maxn = 102;
int map[maxn][maxn], sum[maxn][maxn];
int n;

int read()
{
int i, j;
if(cin >> n)
{
for(i=1;i<=n;++i)
{
sum[i][0] = 0;
for(j=1;j<=n;++j)
{
cin >> map[i][j];
sum[i][j] = map[i][j] + sum[i][j-1];
}
}
return 1;
}
return 0;
}

void solve()
{
int i, j, k, sub_row, max[maxn], min[maxn], best;
best = 0;
for(i=1;i<=n;++i)
{
for(j=i;j<=n;++j)
{
sub_row = 0;
max[0] = 0;
min[0] = 100000;
for(k=1;k<=n;++k)
{
sub_row = sum[k][j] - sum[k][i];
max[k] = MAX(max[k-1], sub_row);
min[k] = MIN(min[k-1], sub_row);
}
best = MAX(max[n] - min[n], best);
}
}

cout << best << endl;
/*for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
cout << map[i][j] << " " << endl;*/
}

int main()
{
while(read()) solve();
return 0;
}