题解 | #最大子矩阵#

简单的思路
求出所有以[i,j]为右下端点的所有矩阵大小，并比较其最值。时间复杂度N^4
dp
对于[i,j]，显然的其所有矩阵是[i+1,j]的子矩阵，多出的部分是第i行的前j个元素。那么我们就可以通过[i,j]求出[i+1,j]
关于求矩阵大小，可以先累加每行，再将行和累加；同样的，先算列和再累加也是一样的。
令sums[i][j][k]为以[i-k]到[i, j]的求和（列和）,那么根据上述两条，可以得到递推公式sums[i][j][k] = (k == 0) ? mat[i][j] : sums[i-1][j][k-1] + mat[i][j]；此时，求sums[i][j][k]的最大累加和，即求得该点所有矩阵的最大值。

#include<iostream>
using namespace std;
const int MAXN = 105;
int n;
int dp[MAXN];
int sums[MAXN][MAXN][MAXN];    //i行j列高为k（k+1）的矩阵和
int getMax(int arr[MAXN], int n){//dp
    int res = dp[0] = arr[0];
    for(int i = 1; i < n; ++i){
        dp[i] = max(dp[i-1], 0) + arr[i];
        res = max(res, dp[i]);
    }
    return res;
}
int main(){
    int val;
    int ans = 0x80000000;    //INT_MIN
    cin >> n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> val;
            for(int k = 0; k <= i; ++k)
                if(k == 0)//这一行
                    sums[i][k][j] = val;
                else
                    sums[i][k][j] = sums[i-1][k-1][j] + val;
        }
    }
    for(int i = 0; i < n; ++i)
        for(int k = 0; k <= i; ++k)
            ans = max(ans, getMax(sums[i][k], n));
    cout << ans;
    
    return 0;
}