题解 | #最大子矩阵#

#include<iostream>

using namespace std;
const int MAXN = 110;

int DP(int a[],int n){//对一个序列求最大子序列
    int dp[MAXN] = {0}, maxResult = -1e9;
    for(int i = 1; i <= n; i++){
        dp[i] = max(dp[i-1]+a[i],a[i]);
        maxResult = max(dp[i],maxResult);
    }

    return maxResult;
}

int main(){
    int n,a[MAXN][MAXN] = {0},S[MAXN];
    while(cin >> n){
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                cin>>a[i][j];
        int maxResult = -1e9;
        for(int i = 1; i <= n; i++){
            int S[MAXN][MAXN] = {0}; //每次新一行开一个新矩阵
            for(int j = i; j <= n; j++){
                for(int k = 0; k <= n; k++){
                    S[j][k] = S[j-1][k] + a[j][k];
                    maxResult = max(maxResult,DP(S[j],n));//i到j行之和的子序列寻找最大序列
                }
            }
        }
        cout<<maxResult<<endl;
    }

    return 0;
}

对于一个矩阵，可以将其转换成一个序列，然后求最大子序列。
具体方法是：
（1）取第i行到第j行之间的元素“拍扁”成一行就成了一个序列。
（2）对这个序列求最大子序列，就得到i行到j行之间可能的最大子矩阵。
（3）遍历所有可能的i和j，就可以得到整个矩阵的最大子矩阵。
要注意在i行到j行“排扁”的过程中可以利用i行到j-1行拍扁的结果：

S[j][k] = S[j-1][k]+a[j][k];

时间复杂度。