题解 | #子矩阵的最大累加和问题#

// 64 位输出请用 printf("%lld")
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int maxSumSubarray(vector<int>& arr, int m) {
    int maxSum = INT_MIN;
    int curSum = 0;
    for (int i = 0; i < m; ++i) {
        curSum += arr[i];
        maxSum = max(maxSum, curSum);
        curSum = (curSum < 0) ? 0 : curSum;
    }
    return maxSum;
}

int maxSumSubmatrix(vector<vector<int>>& mat, int n, int m) {
    int maxSum = INT_MIN;
    for (int i = 0; i < n; ++i) {
        vector<int> arr(m, 0);
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < m; ++k) {
                arr[k] += mat[j][k];
            }
            maxSum = max(maxSum, maxSumSubarray(arr, m));
        }
    }
    return maxSum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    while (cin >> n >> m) {
        vector<vector<int>> mat(n, vector<int>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> mat[i][j];
            }
        }
        cout << maxSumSubmatrix(mat, n, m) << "\n";
    }

    return 0;
}