题解 | #最大子矩阵#

#include<iostream>
#include<algorithm>
using namespace std;
int graph[100][100];
int total[100][100];
int dp[100];
int arr[100];
int MaxS(int n){
    int Max = 0;
    for(int i = 0;i < n;++i){
        if(i == 0)
            dp[i] = arr[i];
        else
            dp[i] = max(arr[i],dp[i - 1] + arr[i]);
        Max = max(dp[i],Max);
    }
    return Max;
}
int MaxMatrix(int n)
{
    int Max = 0;
    for(int i = 0;i < n;++i){
        for(int j = i;j < n;++j){
            for(int k = 0;k < n;++k){
                if(i == 0)
                    arr[k] = total[j][k];
                else
                    arr[k] = total[j][k] - total[i - 1][k];
            }
            int current = MaxS(n);
            Max = max(Max,current);
        }
    }
    return Max;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n){
        for(int i = 0;i < n;++i){
            for(int j = 0;j < n;++j){
                cin >> graph[i][j];
                if(i == 0)
                    total[i][j] = graph[i][j];
                else
                    total[i][j] = total[i - 1][j] + graph[i][j];
            }
        }
        int ans = MaxMatrix(n);
        cout << ans << endl;
    }
}