题解 | #最大子矩阵#
最大子矩阵
https://www.nowcoder.com/practice/a5a0b05f0505406ca837a3a76a5419b3
主要思想在于将多维矩阵降维成为1*n的矩阵，再利用一维数组最大的连续子数组和可以得出
#include <iostream>
#define MAXN 110
#define MIN -99999
using namespace std;
int matrix[MAXN][MAXN];
int help[MAXN][MAXN];//帮助降维辅助数组，help[i][j]表示前i行第j列的和
int arr[MAXN];//保存降维（或未降维）的数组,利于求解最大连续和
int dp[MAXN];
//一维数组最大连续和
int getMaxSequence(int N) {
int res = MIN;
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]);
}
res = max(dp[i], res);
}
return res;
}
//矩阵最大连续和
int getMaxMatrixSequence(int N) {
int res = MIN;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) { //从第i行到第j行
for (int k = 0; k < N; k++) { //第k列
if (i == 0) {
arr[k] = help[j][k];
}
else {
arr[k] = help[j][k] - help[i - 1][k]; //降维
}
}
int tem_res = getMaxSequence(N);
res = max(tem_res, res);
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
int N;
while (cin >> N) {
//初始化结果
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> matrix[i][j];
if (i == 0) {
help[i][j] = matrix[i][j];
} else {
help[i][j] = help[i - 1][j] +
matrix[i][j]; //前i-1行第j列的和加上第i行第j列的和
}
}
}
cout << getMaxMatrixSequence(N) << endl;
}
return 0;
}
