限制

时间限制 : 1 秒

内存限制 : 128 MB

题目

给定一个 n×m 的矩阵 A，求 A 中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A 的子矩阵指在 A 中行和列均连续的一部分。

输入

输入的第一行包含两个整数n,m(1≤n,m≤50)，分别表示矩阵 A 的行数和列数。接下来 n 行，每行 m 个整数，表示矩阵 Ai,j​(−1000≤Ai,j​≤1000)。

输出

输出一行，包含一个整数，表示 A 中最大的子矩阵中的元素和。

样例

输入

3 3
2 -4 1
-1 2 1
4 -2 2

输出

6

代码（优化前）

#include<bits/stdc++.h>
using namespace std;
int a[55][55],ma=INT_MIN;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int x1=1;x1<=n;x1++)
	{
		for(int y1=1;y1<=m;y1++)
		{
			for(int x2=x1;x2<=n;x2++)
			{
				for(int y2=y1;y2<=m;y2++)
				{
					int sum=0;
					for(int i=x1;i<=x2;i++)
					{
						for(int j=y1;j<=y2;j++)
						{
							sum+=a[i][j];
						}
					}
					if(sum>ma)
					{
						ma=sum;
					}
				}
			}
		}
	}
	cout<<ma;
	return 0;
}

代码（优化后）

#include<bits/stdc++.h>
using namespace std;
int a[55][55];
int suma[55][55];
int main()
{
	int n,m,ma=INT_MIN;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			suma[i][j]=suma[i-1][j]+suma[i][j-1]-suma[i-1][j-1]+a[i][j];
		}
	}
	for(int x1=1;x1<=n;x1++)
	{
		for(int y1=1;y1<=m;y1++)
		{
			for(int x2=x1;x2<=n;x2++)
			{
				for(int y2=y1;y2<=m;y2++)
				{
					int s=suma[x2][y2]-suma[x1-1][y2]-suma[x2][y1-1]+suma[x1-1][y1-1];
					if(s>ma)
					{
						ma=s;
					}
				}
			}
		}
	}
	cout<<ma;
	return 0;
}