题解 | 最大子矩阵

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
const int N = 110;
int graph[N][N];
int s[N][N];//保存每一列的前缀和
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &graph[i][j]);
	//求每一列的前缀和
	for (int j = 1; j <= n; j++)
		for (int i = 1; i <= n; i++) {
			s[i][j] = s[i - 1][j] + graph[i][j];
		}

	//枚举上下边界
	int res = 0xc0c0c0c0;
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++) {
			/*int f = 0;*/
			//现在要开始用dp求最大连续子序列，以第i个为一组和i个以前的为一组进行划分
			//可以得到f[i]=max(f[i-1]+w[i],w[i])
			//然后将w[i]提出来可以得到
			//max(f[i-1],0)+w[i]
			//由于每个只与上一个状态有关，所以也不用状态数组，用一个f来表示上一个状态的值即可
			int f = 0;
			for (int k = 1; k <= n; k++) {
				//k说明在两条边界之间的列好
				int w = s[j][k] - s[i - 1][k];//注意这里是s[i-1][k]
				f = max(f, 0) + w;
				res = max(f, res);
			}
		}
	printf("%d", res);
	return 0;
}