#include<bits/stdc++.h>
using namespace std;
const int N=205;
int a[N][N],b[N],dp[N],n;
int sub_sum(){
	int ma=INT_MIN; 
	dp[1]=b[1]; //动态转移方程的边界
	//求dp数组中最大连续子序列和 
	for(int i=2;i<=n;i++){
		dp[i]=max(dp[i-1]+b[i],b[i]);
	} 
	for(int i=1;i<=n;i++){ //求dp数组中的最大值 
		ma=max(ma,dp[i]);
	}
	return ma;
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	//对二维数组状态压缩
	int max_sum=a[1][1];
	for(int i=1;i<=n;i++){
		memset(b,0,sizeof(b));
		//开始压缩
		for(int j=i;j<=n;j++){
			for(int z=1;z<=n;z++){
				b[z]+=a[j][z];
			}
			//对b数组求最大连续子序列和
			int s=sub_sum(); //写函数 
			if(s>max_sum){
				max_sum=s;
			} 
		} 
	} 
	//输出
	cout<<max_sum<<endl; 
	return 0;
}


4 条评论

  • 1

信息

ID
2164
时间
1000ms
内存
256MiB
难度
9
标签
递交数
87
已通过
13
上传者