题解 | 最大子矩阵

#include <bits/stdc++.h>
using namespace std;
int N, A[105][105], sum[105][105], column[105], maxS = INT_MIN;

// 最大子数组和
int calculate(){
    vector<int> dp(N + 1);
    int ret = INT_MIN;
    for(int i = 1; i <= N; i++){
        dp[i] = max(column[i], dp[i - 1] + column[i]);
        ret = max(ret, dp[i]);
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> A[i][j];
            sum[i][j] = sum[i - 1][j] + A[i][j]; // 计算每列的前缀和
        }
    }

    for(int i = 1; i <= N; i++){ // 起始行
        for(int j = i; j <= N; j++){ // 终止行
            for(int k = 1; k <= N; k++){ // 计算 i~j行 第k列的和
                column[k] = sum[j][k] - sum[i - 1][k];
            }
            maxS = max(maxS, calculate());
        }
    }
    cout << maxS;

    return 0;
}