题解 | #最大子矩阵#

#include <climits>
#include <iostream>
#include <cstring>

using namespace std;



/*暴力解：
枚举每个左上角（a,b）于右下角（c，d）
用前缀和，时间复杂度：O（n^4） 10^8

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]

子矩阵abcd的和：
ans = sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]
*/
const int N = 110;
int arr[N][N];
int sum[N][N];

int main() {
    int n;
    cin >> n;
    memset(arr, 0, sizeof(arr));
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    //计算前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    //计算最大子矩阵和
    int ans = INT_MIN;
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int c = a; c <= n; c++) {
                for (int d = b; d <= n; d++) {
                    ans = max(ans, sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
                }
            }
        }
    }
    cout << ans << endl;


    return 0;
}