题目描述

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

样例

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

8  0 -2

输出样例：
15

还是一道模板题…
只需用二维前缀和预处理一下.
再枚举子矩阵的左上角和右下角,再取其中权值最大的即可.

时间复杂度 $O(n^4)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 110
#define INF 0x7fffffff
#define ll long long
using namespace std;
int Map[N][N],n,sum[N][N],ans=-INF;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&Map[i][j]);
            sum[i][j]=Map[i][j];
        }
    for(int i=1;i<=n;i++)//前缀和处理
        for(int j=1;j<=n;j++){
            if(i==1&&j==1)
                continue;
            else if(i==1)
                sum[i][j]+=sum[i][j-1];
            else if(j==1)
                sum[i][j]+=sum[i-1][j];
            else
                sum[i][j]+=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]);
        }
    for(int i=1;i<=n;i++)//枚举子矩阵的左上角和右下角坐标
        for(int j=1;j<=n;j++)
            for(int k=i;k<=n;k++)
                for(int l=j;l<=n;l++){
                    int num=(sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1]);//计算子矩阵的权值
                    ans=max(ans,num);//更新答案
                }
    printf("%d\n",ans);
    return 0;
}