MATRIX

As we all know, we live inside the matrix that is divided into N rows and N columns. An integer is
written into each one of the NxN cells of the matrix. In order to leave the matrix, we must find the
most beautiful square (square-shaped sub-matrix) contained in the matrix.
If we denote by A the sum of all integers on the main diagonal of some square, and by B the sum of
the other diagonal, then the beauty of that square is A - B.
Note: The main diagonal of a square is the diagonal that runs from the top left corner to the bottom
right corner.
INPUT
The first line of input contains the positive integer N (2 ≤ N ≤ 400), the size of the matrix.
The following N lines each contain N integers in the range [-1000, 1000], the elements of the matrix.
OUTPUT
The only line of output must contain the maximum beauty of a square found in the matrix.

SAMPLE TESTS
input

2
1 -2
4 5

output

4
input

3
1 2 3
4 5 6
7 8 9

output

0
input

3
-3 4 5
7 9 -2
1 0 -6

output

5

Solution:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int N;
int a[401][401];
int res = -8000000;

int main()
{
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);

scanf("%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
scanf("%d",&a[i][j]);
// res = max(res,a[i][j]);
}
int ii,jj;
int dd;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
for(int d=2;d<=N;d++)
{
if(i+d-1>N || j+d-1 >N) continue;
int temp = 0;
ii = i;
jj = j;
dd =  1;
while(dd<=d)
{
temp += a[ii][jj];
ii++;
jj++;
dd++;
}

ii = i;
jj = j-1+d;
dd = 1;
int temp_ = 0;
while(dd<=d)
{
temp_ += a[ii][jj];
ii++;
jj--;
dd++;
}
res = max(res,temp-temp_);
}
}
cout << res;
return 0;
}

Độ phức tạp. O(N^3). Có thể làm thành O(N^2) nếu sử dụng kỹ thuật PreCompute.