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

`}`

There is a problem about your solution: for this problem, you can't have a empty rectangle, so the maximum must be negative if all the numbers are negative. For example, your code will output 0 for this test: 2 -1 -1 -1 -1, and the true answer is -1.

ReplyDelete