**问题描述 有一个N*N的矩阵, 找出它的美丽值最大的子矩阵, 要求这个子矩阵是正方形, 即长和宽相等。

定义一个矩阵的美丽值为：将这个矩阵主对角线上的数的和定义为A, 另一条对角线上的数的和定义为 B, 则这个矩阵的美丽值为 A-B 。

输入格式 输入的第一行包含一个正整数N 。

接下来N 行每行包含 N 个整数, 表示这个矩阵。

1<=N<=400, -10000<=矩阵元素<=10000 。

输出格式 输出一行一个整数，表示最大的美丽值。

样例输入 1 2 1 -2 4 5

样例输出 1 4

样例输入 2 3 1 2 3 4 5 6 7 8 9

样例输出 2 0

样例输入 3 3 -3 4 5 7 9 -2 1 0 -6

样例输出 3 5 **

---

代码：

#include<bits/stdc++.h>
using namespace std;

int n,a[500][500],Left[500][500],Right[500][500];

int query(int x,int y,int r)
{
	if(x-r+1>0 && y-r+1>0)
		return (Left[x][y]-Left[x-r][y-r])-(Right[x][y-r+1]-Right[x-r][y+1]);
	return -INT_MAX;
}

signed main()
{
//	freopen("txt.in","r",stdin);
//	freopen("txt.out","w",stdout);
	memset(Right,0,sizeof Right);
	memset(Left,0,sizeof Left);
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	
	if(n==1)
	{
		cout<<a[1][1]<<endl;
		return 0;
	}
	
	for(int i=1;i<=n;i++)
	{
		Left[1][i]=a[1][i];
		int lj=i,li=1;
		while(lj<=n && li<=n)
		{
			Left[li+1][lj+1]=Left[li][lj]+a[li+1][lj+1];
			li++;lj++;
		}
		Right[1][n-i+1]=a[1][n-i+1];
		int ri=1,rj=n-i+1;
		while(ri<=n && rj>=1)
		{
			Right[ri+1][rj-1]=Right[ri][rj]+a[ri+1][rj-1];
			ri++;rj--;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(Left[i][1]==0)
		{
			Left[i][1]=a[i][1];
			int lj=1,li=i;
			while(lj<=n && li<=n)
			{
				Left[li+1][lj+1]=Left[li][lj]+a[li+1][lj+1];
				li++;lj++;
			}
		}
		if(Right[i][n]==0)
		{
			Right[i][n]=a[i][n];
			int ri=i,rj=n;
			while(ri<=n && rj>=1)
			{
				Right[ri+1][rj-1]=Right[ri][rj]+a[ri+1][rj-1];
				ri++;rj--;
			}
		}
	}
	
	cout<<endl<<endl<<endl;
 
// for(int i=1;i<=n;i++)
// {
//  for(int j=1;j<=n;j++)
//   cout<<Left[i][j]<<' ';
//  cout<<endl;
// }
// 
// cout<<endl<<endl<<endl;
// for(int i=1;i<=n;i++)
// {
//  for(int j=1;j<=n;j++)
//   cout<<Right[i][j]<<' ';
//  cout<<endl;
// }
// cout<<endl<<endl<<endl;
	
	int ans=-INT_MAX;
	
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			for(int k=2;k<=min(i,j);k++)
			{
				ans=max(ans,query(i,j,k));
			}
		}
	} 
	
	cout<<ans<<endl;
	
	return 0;
} 
 

WA:90

oi:NKOJ