题目描述

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为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*N的整数数组。

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

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

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

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

数据范围
1≤N≤100

样例

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

8  0 -2
输出样例：
15

算法1

(暴力枚举) $O(n^3)$

具体看代码

时间复杂度

O(n^3)

参考文献

C++ 代码

//首先暴力,用前缀和维护,枚举矩阵的两个顶点O(n^4).
//正解的话首先考虑一维:a1,a2,a3,a4..an
//我们可以开一个临时变量now扫一遍,对于每一个数,先加上去,更新答案,如果now小于0,就把now赋为0.
//什么意思呢,因为now已经小于0了,说明前面的累加值已经是负数了,继续累加上去已经没有意义,不如从这断开,这时新的累加值即为0
//之后我们拓展到为二维,我们可以把每一列压缩成一个值,这样就转化成一维的了.
//具体实现看代码 
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N],n,a[N][N],ans=-(1<<30);
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
int main()
{
    n=read();
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n;++j) a[i][j]=read();
    for(int i=1;i<=n;++i)
    {
        memset(f,0,sizeof(f));//表示每一列的压缩值.
        for(int j=i;j<=n;++j)
        {
            for(int k=1;k<=n;++k) f[k]+=a[j][k];
            int now=0;
            for(int k=1;k<=n;++k)
            {
                now+=f[k];
                ans=max(ans,now);
                if(now<0) now=0;
            }
        }
    }
    printf("%d",ans);
    return 0;
}