UVa 108

This is a well known problem. Also called Kadane's 2D problem, it asks to find the maximum sub matrix from a given matrix of integers. The theory is to reduce it to Kadane's 1D problem which aims at finding the maximum sub array in a given array of integers. How do we reduce, this is how:

1) First find the column sums, can be done on the fly. O(n^2)

2) Then just chose pair of rows from this table of column sums. O(n^2)

3) For each pair selected find the partial sum of each column from 1 to n

4) Run Kadane's 1D on the 1D array found above. O(n)

5) Voila sub matrix found in O(n^3)

Here it goes:

#include<stdio.h>

#include<algorithm>

using namespace std;

int tab[101][101];

int main() {

int n;

while(scanf("%d",&n)==1) {

for(int i=1;i<=n;++i) {

for(int j=1;j<=n;++j) {

scanf("%d",&tab[i][j]);

tab[i][j]+=tab[i-1][j];

}

}

int mx=tab[1][1];

for(int i=0;i<n;++i) {

for(int j=i+1;j<=n;++j) {

int temp=0;

for(int k=1;k<=n;++k) {

temp+=tab[j][k]-tab[i][k];

if(temp<0) temp=0;

mx=max(mx,temp);

}

}

}

printf("%d\n",mx);

}

return 0;

}