To the Max

The input consists of an N*N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by $N^2$ integers separated by whitespace (spaces and newlines). These are the $N^2$ integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 484K, 提交时间: 2020-05-17 19:05:10

#include<bits/stdc++.h>
using namespace std;
const int N=110;

int g[N][N],n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		scanf("%d",&g[i][j]);
		g[i][j]+=g[i-1][j];
	}
	int res=INT_MIN;
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
	{
		int last=0;
		for(int k=1;k<=n;k++)
		{
			last=max(last,0)+g[j][k]-g[i-1][k];
			res=max(res,last);
		 } 
	}
	printf("%d\n",res);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 376K, 提交时间: 2020-01-29 16:01:11

#include<bits/stdc++.h>
using namespace std;
int n,Max,sum,a[105][105];
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){cin>>a[i][j];a[i][j]+=a[i][j-1];}
	for(int i=0;i<n;++i)
		for(int j=i+1;j<=n;++j){
			sum=0;
			for(int k=1;k<=n;++k){
				sum+=a[k][j]-a[k][i];
				Max=max(Max,sum);
				sum=max(sum,0);
			}
		}
	cout<<Max<<endl;
	return 0;
}

详情