题目描述

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

使用前缀和直接枚举每一个矩阵，只需要枚举每一个矩阵的四个顶点x1 y1 x2 y2即可，一看数据范围只有$100$，区区$10^8$的复杂度搞不好能过，而且常数还很小，所以就真的过了/大雾。

时间复杂度

$O(n^4)$

C++ 代码

#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], s[N][N], n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> a[i][j], s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    int maxn = -2e9;
    for(int x1 = 1; x1 <= n; x1 ++)
        for(int y1 = 1; y1 <= n; y1 ++)
            for(int x2 = x1; x2 <= n; x2 ++)
                for(int y2 = y1; y2 <= n; y2 ++)
                    maxn = max(maxn, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    cout << maxn;

}

算法2

(dp) $O(n^3)$

C++ 代码

#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> a[i][j], a[i][j] += a[i - 1][j];
    int res = -2e9;
    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)
        {
            int last = 0;
            for(int k = 1; k <= n; k ++)
            {
                last = max(last, 0) + a[j][k] - a[i - 1][k];
                res = max(res, last);
            }
        }
    cout << res << endl;
}