题解 | 最大子矩阵

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int kadane(vector<int>& arr){
    int n=arr.size();
    int mx_current=arr[0];
    int mx_global=arr[0];
    for(int i=1;i<n;i++){
        // -7 5 -8 3 4
        mx_current=max(mx_current+arr[i],arr[i]);//找到每行相加最大值
        if(mx_current>mx_global) mx_global=mx_current;
    }
    return mx_global;
}
int main() {
    int n;
    cin>>n;
    vector<vector<int>> arr(n,vector(n,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
        }
    }
    int maxValue=INT_MIN;
    for(int topRow=0;topRow<n;topRow++){
        vector<int> colSum(n,0);
        for(int bottleRow=topRow;bottleRow<n;bottleRow++){
            for(int col=0;col<n;col++){
                colSum[col]+=arr[bottleRow][col];//按列从首行到尾行数据求和
            }
            int curMax=kadane(colSum);
            if(curMax>maxValue){
                maxValue=curMax;
            }
        }
    }
    cout<<maxValue;
    return 0;
}
// 64 位输出请用 printf("%lld")