题解 | 最大子矩阵

#include <iostream>
#include <climits>

using namespace std;

const int MAX_N = 100;  // 题目中 N <= 100
int matrix[MAX_N][MAX_N];
int temp[MAX_N];  // 用于列压缩

// 求解最大子数组和（Kadane's Algorithm）
int maxSubarraySum(int arr[], int n) {
    int max_sum = INT_MIN, cur_sum = 0;
    for (int i = 0; i < n; ++i) {
        cur_sum = max(arr[i], cur_sum + arr[i]);
        max_sum = max(max_sum, cur_sum);
    }
    return max_sum;
}

// 计算最大子矩阵和
int maxSubmatrixSum(int N) {
    int max_sum = INT_MIN;

    // 枚举上边界
    for (int top = 0; top < N; ++top) {
        // 清空列压缩数组
        for (int i = 0; i < N; ++i) temp[i] = 0;

        // 枚举下边界
        for (int bottom = top; bottom < N; ++bottom) {
            // 计算 top 到 bottom 行的列和
            for (int col = 0; col < N; ++col) {
                temp[col] += matrix[bottom][col];
            }

            // 求解最大子数组和
            max_sum = max(max_sum, maxSubarraySum(temp, N));
        }
    }

    return max_sum;
}

int main() {
    int N;
    cin >> N;

    // 读取矩阵
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> matrix[i][j];
        }
    }

    // 计算并输出最大子矩阵和
    cout << maxSubmatrixSum(N) << endl;

    return 0;
}