主要思想在于将多维矩阵降维成为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; }