子矩阵最大和

vector<vector<int>> CalculateMap(vector<vector<int>> mat)
{
	vector<vector<int>> map(mat.size(),vector<int>(mat.front().size(),0));
	for (int i = 0; i < mat.size(); i++)
	{
		for (int j = 0; j < mat.front().size(); j++)
		{
			if (i==0&&j==0)
			{
				map[i][j]=mat[i][j];
			}
			else if (i==0)
			{
				map[i][j]=map[i][j-1]+mat[i][j];
			}
			else if (j==0)
			{
				map[i][j]=map[i-1][j]+mat[i][j];
			}
			else
			{
				map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]+mat[i][j];
			}
		}
	}
	return map;
}
int CalculateSum(vector<vector<int>> mat,int i,int j,int k ,int w,vector<vector<int>> map)
{
	int sum;
	if (i==0&&k==0)
	{
		sum=map[j][w];
	}
	else if (i==0)
	{
		sum=map[j][w]-map[j][k];
	}else if (k==0)
	{
		sum=map[j][w]-map[i][w];
	}
	else
	{
		sum=map[j][w]-map[i-1][w]-map[j][k-1]+map[i-1][k-1]    ;
	}
	                                            ;
	return sum;
}
int sumOfSubMatrix(vector<vector<int> > mat, int n)
{
	int MaxSum=mat.front().front();
	vector<vector<int>> map;
	map=CalculateMap(mat);
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				for (int w = k; w < n; w++)
				{
					if (CalculateSum(mat,i,j,k,w,map)>MaxSum)
					{
						MaxSum=CalculateSum(mat,i,j,k,w,map);
					}
				}
			}
		}
	}
	return MaxSum;
}