题解 | #最大子矩阵#

比机试指南上面的代码清晰一些

#include <cstdio>
#include <iostream>
#include <climits>
#include <cstring>

using namespace std;

const int MAXN = 100 + 10;

const int INF = INT_MAX;

int matrix[MAXN][MAXN];
int dp[MAXN];
int coltotal[MAXN][MAXN];//概率论中“分布函数”的感觉
int arr[MAXN];

int MaxSubsequence(int n){
	fill(dp, dp+n, -INF);
	int ans = -INF;
	for(int i=0; i<n; i++){
		if(i==0){
			dp[i] = arr[i];
		}else{
			dp[i] = max(arr[i], dp[i-1] + arr[i]);
		}
		if(dp[i] > ans){
			ans = dp[i];
		}
	}
	return ans;
}

int MaxSubmatrix(int m, int n){
	for(int j=0; j<n; j++){
		coltotal[0][j] = matrix[0][j];
	}
	for(int i=1; i<m; i++){
		for(int j=0; j<n; j++){
			coltotal[i][j] = matrix[i][j] + coltotal[i-1][j];
		}
	}//至此都是在初始化coltotal，这件事情在答案中是在main里面做的 
	int ans = -INF; 
	for(int i=0; i<m; i++){//定位到某一行 
		for(int j=i; j<m; j++){//也是定位到某一行。
			for(int k=0; k<n; k++){//定位到某一列。本列中i行至j行的元素之和存入arr[k]以使用Subsequence的方法
									//求和的方式：就用到了那个分布函数的思想，coltotal这一完美设计
									//这样子写代码，比书上那个例题答案清晰太多了 
				if(i==0){
					arr[k] = coltotal[j][k];
				}else{
					arr[k] = coltotal[j][k] - coltotal[i-1][k];
				}
			}//此时本轮arr的填充结束，可以执行一次MaxSubsequence
			int tmp = MaxSubsequence(n);
			if(tmp > ans){
				ans = tmp;
			}
		}
	}
	return ans;
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				scanf("%d", &matrix[i][j]);
			}
		}
		int ans = MaxSubmatrix(n, n);
		printf("%d\n", ans);
	}
	return 0;
}