题解 | #最大子矩阵#

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//  知识点：前缀和 和 动态规划
int main() {
    int n;
    cin >> n;
    int nums[n + 1][n + 1], dp[n + 1][n + 1];
    memset(nums, 0, sizeof(nums));    // 一定要初始化！！！，否则会出错
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> nums[i][j];
            dp[i][j] = dp[i - 1][j] + nums[i][j];  // dp[i][j] 统计j列前i个nums的总和
        }
    }
    int ans = INT_MIN;    // ans 初始化为INT_MIN，保证有正确输出
    for (int i1 = 1; i1 <= n; i1++) {
        for (int i2 = i1; i2 <= n; i2++) {
            int sum[n + 1];
            memset(sum, 0, sizeof(sum));
            for (int j = 1; j <= n; j++) {
                int temp = dp[i2][j] - dp[i1 - 1][j];    // temp为j列[i1,i2]的和
                sum[j] = max(sum[j - 1] + temp, temp);   // sum为动态规划求最大矩阵
                ans = max(ans, sum[j]);    // 比较各矩阵大小 
            }
        }
    }
    cout << ans << endl;     // 输出答案
    return 0;
}