题解 | #最大子矩阵#

#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;
}