Please give me some example where my program gives bad result
I calculated every sum by columns and then used dp for finding largest in rows, I know there is an easy O(N^4) solution but I want this one

#include <stdio.h>

long i,j,k,n,max=-150,tmp=0,a[200][200];

main () {
     scanf ("%d",&n);
     for (i=0;i<n;i++)
         for (j=0;j<n;j++) {
             scanf ("%d",&a[i][j]);
             if (a[i][j]>max) max=a[i][j];}
     for (k=0;k<n;k++) {
         if (k!=0)
            for (i=n-1;i>=k;i--)
                for (j=0;j<n;j++)
                    a[i][j]-=a[i-1][j];
         for (i=k+1;i<n;i++)
             for (j=0;j<n;j++)
                 a[i][j]+=a[i-1][j];
         for (i=k;i<n;i++){
             tmp=0;
             for (j=0;j<n;j++){
                 tmp+=a[i][j];
                 if (max<tmp) max=tmp;
                 while (tmp<0) tmp=a[i][j++];
             }
             if (max<tmp) max=tmp;
         }
     }
     printf ("%d",max);
}

Edited by author 03.11.2007 03:39

Edited by author 03.11.2007 03:39