感谢@ctq1999指出本题解代码不宜巨佬学习,所以萌新我修改了一波代码,变成了萌新版代码.

题目描述

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中，具有最大和的子矩形被称为最大子矩形。

例如，下列数组：

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 

其最大子矩形为：

9 2 
-4 1 
-1 8 

它拥有最大和15。

输入格式
输入中将包含一个$N^2$的整数数组。

第一行只输入一个整数N，表示方形二维数组的大小。

从第二行开始，输入由空格和换行符隔开的$N^2$个整数，它们即为二维数组中的$N^2$个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。

数组中的数字会保持在$[-127,127]$的范围内。

输出格式
输出一个整数，代表最大子矩形的总和。

数据范围
$1≤N≤100$

样例

输入样例：
4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2
输出样例：
15

贪心+前缀和

解题思路:首先我们容易想到,可以枚举矩阵的左上角$(x_1,y_1)$和右下角$(x_2,y_2)$ ,然后通过二维前缀和算出矩阵和,这样就可以确定我们所需要的矩阵,但是时间复杂度是$O(n^4)$,这样的复杂度太大了,我们无法解决.所以我们可以换一种思想,贪心处理.问题是我们怎么贪心了, 大致可以这样大力贪心

首先我们自行模拟一遍矩阵,发现一个重要的性质就是,如果说当前的答案加上当前这一排让我们当前的ans值小于0的话,那么这一排包括这一排上面的数值,我们都可以不要了,因为如果我们选择了上面的矩阵,还不如不去选择这个矩阵.这一点比较难以理解,我们画一个图理解一下.

感谢@昂昂累世士大佬和一个月前私信告诉我的@wulai大佬指出,本题解有一个小Bug,初始化的ans最小值因为一个特别小的负数.
这里提供一组Hack数据,稍后应该会加入数据库吧.
输入

4
-3 -2 -7 -7 -9 -2 -6 -2
-4 -1 -4  -1 -1
-8  -4 -2

输出

-1

C++ 代码

//之前有大佬说,define不宜萌新学习,所以萌新我决定稍微修改了代码
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N],s[N][N],n,m,i,j,ans=-1e8,now_ans;
bool ok=false;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if (a[i][j]>=0)
                ok=true;
            ans=max(ans,a[i][j]);
        }
    if (!ok)//注意特殊判定
    {
        cout<<ans;
        return 0;
    }
     for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++)
            s[i][j]=s[i-1][j]+a[i][j];
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
        {
            now_ans=0;
            for(int l2=1;l2<=n;l2++)
            {
                now_ans+=s[r][l2]-s[l-1][l2];
                if (now_ans<0)
                    now_ans=0;
                if (now_ans>ans)
                    ans=now_ans;
            }
        }
    cout<<ans;
    return 0;
}