题解 | #最大子矩阵#

#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;

/*
    最大子矩阵：
    1. 单行(i)->转化为最大子序列
    2. 多行(i-j)->将第i行到第j行所有行元素相加得到一维数组，这个一维数组的最大子序列和就是最大子矩阵和
    3. 只需从小到大一次枚举并遍历i和j，接着输出所有子矩阵中的最大值
    4. 可以事先用一个辅助二维数组记录从第一行到第i行的累加值，求i到j行的累加值时只需要做一次减法即可
*/

const int MAXN = 101;
const int MINN = -INT_MAX;
int assist[MAXN][MAXN];
int arr[MAXN][MAXN];
int seq[MAXN];
int dp[MAXN]; // 以第i行结束的矩阵的最大子矩阵的和

//创建辅助矩阵assist，储存以第i行结尾的子矩阵之和的序列
void BuildAssist(int n){
    int tmp[n];
    for(int i=0; i<n; ++i)
        tmp[i] = 0;

    for(int i=0; i<=n; ++i){ //assist第0行全设为0，方便后面相减
        for(int j=0; j<=n; ++j){
            assist[i][j] = tmp[j];
            if(i < n)
                tmp[j] += arr[i][j];
        }
    }
    for(int i=0; i<n; ++i)
        seq[i] = arr[0][i];
}

//计算某一行序列的最大子串和
int MaxSeq(int n){
    dp[0] = seq[0];
    for(int i=1; i<n; ++i){
        dp[i] = max(seq[i], dp[i-1]+seq[i]);
    }
    int res = dp[0];
    for(int i=0; i<n; ++i){
        if(res<dp[i]) res = dp[i];
    }
    return res;
}

int MaxMatrix(int n){
    int res, matrixMax = -INT_MAX;
    //从第一行开始枚举，计算以第i行结尾的最大子矩阵的和
    for(int i=1; i<=n; ++i){
        for(int j=0; j<i; ++j){
            for(int k=0; k<n; ++k){
                seq[k] = assist[i][k]-assist[j][k];
            }
            res = MaxSeq(n);
            if(res>matrixMax) matrixMax = res;
        }
    }

    return matrixMax;
}


int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cin>>arr[i][j];
    BuildAssist(n);
    int res = MaxMatrix(n);
    cout<<res<<endl;
}