题解 | #最大子矩阵#

#include<iostream>
using namespace std;

const int maxn=101;
int matrix[maxn][maxn];
int total[maxn][maxn];	//辅助数组，记录列和 
int arr[maxn];			//记录i-j行列和 
int dp[maxn];			//进行动态规划的数组 

int getmaxdp(int n){	//由arr数组计算其最大子序列 
	dp[0]=arr[0];
	int maximum=dp[0];
	for(int i=1;i<n;i++){
		dp[i]=max(arr[i],dp[i-1]+arr[i]);
		maximum=max(maximum,dp[i]);
	} 
	return maximum;
}

void gettotal(int n){	//用于计算total数组 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==0){
				total[i][j]=matrix[i][j];
			}else{
				total[i][j]=total[i-1][j]+matrix[i][j];
			}
		}
	}
	return;
}

int getmaxmatrix(int n){	//计算最大子矩阵 
	int maximum=matrix[0][0];
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			for(int k=0;k<n;k++){	//计算i-j行的列和 
				if(i==0){
					arr[k]=total[j][k];
				}else{
					arr[k]=total[j][k]-total[i-1][k];
				}
			}
			int current=getmaxdp(n);
			maximum=max(maximum,current);
		}
	}
	return maximum;
}

int main(){
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>matrix[i][j];
			}
		}
		gettotal(n);
		cout<<getmaxmatrix(n)<<endl;
	}
	return 0;
}