题解 | #最大子矩阵#

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

//求一维数组的最大连续子数列的值
int getOneDimFunc(int arr[],int n){
    int dp[n];
    dp[0] = arr[0];
    for(int i =1;i<n;i++){
        dp[i] = max(arr[i],arr[i]+dp[i-1]);
    }
    int max = INT_MIN;
    for(auto a:dp){
        if(a>max)max = a;
    }
    return max;
}

int main() {
    int n;
    while(cin>>n){
        int arr[n][n];//声明一个矩阵
        for(int i =0;i<n;i++)
            for(int j =0;j<n;j++)
                cin>>arr[i][j];
        //取dp
        vector<int>dp;
        for(int i =0;i<n;i++){
            for(int j =i;j<n;j++){
                //i,j均表示行号
                if(i == j){
                    //在一行内
                    //直接把该行传入
                    dp.push_back(getOneDimFunc(arr[i],n));
                }else{
                    //不在同一行内，把两个行之间的所有元素作一维化(压缩，不是拉长)
                    vector<int>temp;
                    //按列遍历
                    for(int x=0;x<n;x++){
                        int tt=0;
                        for(int k=i;k<=j;k++){
                            tt+=arr[k][x];
                        }
                        temp.push_back(tt);
                    }
                    //传参
                    dp.push_back(getOneDimFunc(&temp[0],temp.size()));
                }
            }
        }
        //输出v中最大值
        cout<<*max_element(dp.begin(),dp.end());
    }
}
// 64 位输出请用 printf("%lld")

思路来源：BV1cw411f7Rf

本来仿着王道的思路写的，结果自测一直出11...debug找不出原因就换思路了