I haven't idea how to approach this test?
my code is simple O(n^4),but #9 test doesn' work:

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

            s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];



    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        {
            for (k=i;k<=n;k++)
            {
                for (m=j;m<=n;m++)
                {
                    sum=s[k][m]-s[i-1][m]-s[k][j-1]+s[i-1][j-1];

                    if (sum>max1) max1=sum;

                }
            }
        }

Same thing here!

I had the same problem. Firstly I used array of short and there was overflow in sum (max possible sum is 127 * 100 * 100 = 1270000 > 32767). Then I changed type to int and got AC :)