题解 | #最大子矩阵#

#include <climits>
#include <iostream>
using namespace std;
//最大值初始化位最小值
int dp[100][100];
int temp[100][100];
int N;
//ij是起始坐标
void func(int i,int j,int &maxv)
{
    temp[i][j]=dp[i][j];
    //纵向--起始坐标那一竖
    for(int x=i+1;x<N;x++)
    {
        temp[x][j]=temp[x-1][j]+dp[x][j];
        if(temp[x][j]>maxv) maxv=temp[x][j];
    }
    //横向--起始坐标那一横
    for(int y=j+1;y<N;y++)
    {
        temp[i][y]=temp[i][y-1]+dp[i][y];
        if(temp[i][y]>maxv) maxv=temp[i][y];
    }
    //计算以ij为起始的各个二维前缀和
    for(int x=i+1;x<N;x++)
    {
        for(int y=j+1;y<N;y++)
        {
            temp[x][y]=temp[x-1][y]+temp[x][y-1]-temp[x-1][y-1]+dp[x][y];
            if(temp[x][y]>maxv) maxv=temp[x][y];
        }
    }
}
int main()
{
    while(cin>>N)
    {
        //处理输入
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                cin>>dp[i][j];
            }
        }
        //挨个作为矩阵前缀和的起始坐标
        int maxv=dp[0][0];//假设坐标00，大小1X1的矩阵就是目标
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                //看看起始坐标大小
                maxv=max(maxv,dp[i][j]);
                func(i,j,maxv);
            }
        }
        cout<<maxv<<endl;
    }
}
// 64 位输出请用 printf("%lld")