题解 | 最大子矩阵

#include <bits/stdc++.h>
using namespace std;

int maxSubmatrixSum(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;

    int rows = matrix.size();
    int cols = matrix[0].size();
    int maxSum = INT_MIN;

    // 辅助数组用于存储每一列的和
    vector<int> helper(rows, 0);

    // 遍历所有可能的列范围
    for (int left = 0; left < cols; ++left) {
        // 清零辅助数组
        fill(helper.begin(), helper.end(), 0);

        for (int right = left; right < cols; ++right) {
            // 增加当前列到辅助数组
            for (int i = 0; i < rows; ++i) {
                helper[i] += matrix[i][right];
            }

            // 在辅助数组上应用Kadane算法
            int currentSum = 0, localMax = INT_MIN;
            for (int i = 0; i < rows; ++i) {
                currentSum = max(helper[i], currentSum + helper[i]);
                localMax = max(localMax, currentSum);
            }

            maxSum = max(maxSum, localMax);
        }
    }

    return maxSum;
}

int main(){
    int n;
    while(cin>>n){
        vector<vector<int>> matrix(n,vector<int>(n));//初始化一个二维vector，内部不需要命名
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>matrix[i][j];
            }
        }
        cout<<maxSubmatrixSum(matrix)<<endl;
    }
}

这是抄的大佬的，正在研究二维dp，感觉这个问题有点难