题解 | #最大子矩阵#

思路很难想，纯纯的背诵题
#include<iostream>
#include<vector>
#include<limits>
#include<algorithm>
using namespace std;
#define N 105


long long matrix[N][N];
long long total[N][N];  //用于辅助计算
long long dp[N];
long long arr[N];

long long Maxlength(int n) {
	long long maximal = -1000000;
	for (int i = 0; i < n; i++) {
		if (i == 0) dp[i] = arr[i];
		else {
			dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		}
		maximal = max(maximal, dp[i]);
	}
	return maximal;


}

long long Maxsubmatrix(int n) {
	long long maximal = -1000000;
	for (int i = 0; i < n; i++) { // 每k列中前i到j行的所有和中求最大值
		for (int j = i; j < n; j++){
			for (int k = 0; k < n; k++)
			{
				if (i == 0) {
					arr[k] = total[j][k];
				}
				else
					arr[k] = total[j][k] - total[i - 1][k];
			}
		long long temp = Maxlength(n);
		maximal = max(temp, maximal);
        }
	}
		
	return maximal;

}

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];
			}
		}
		// 计算辅助数组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];
				}


			}
		}
		long long res = Maxsubmatrix(n);
		cout << res << endl;
	}
}