最大的和

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

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

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

例如,下列数组:

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

其最大子矩形为:

1
2
3
9 2 
-4 1
-1 8

它拥有最大和 $15$。

输入格式

输入中将包含一个 $N×N$ 的整数数组。

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

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

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

输出格式

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

数据范围

$1≤N≤100$

输入样例:

1
2
3
4
5
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1

8 0 -2

输出样例:

1
15

题目解析

暴力很简单,赶牛入圈的代码拿过来直接用,但是很明显会TLE

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <iostream>

const int N = 105;
int arr[N][N], sum[N][N];

int n;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &arr[i][j]);
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
}
}

int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int x1 = 1, x2 = 1; x2 <= n; x2++) {
while(x2 - x1 > i) x1++;
for (int y1 = 1, y2 = 1; y2 <= n; y2++) {
while(y2 - y1 > j) y1++;
ans = std::max(ans, sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
}
}
}
} printf("%d\n", ans);
return 0;
}

优化一下,通过枚举 上下边界 和 右边界 来计算最大值,我们确定上下边界之后,再用前缀和将二维转化为一维,然后再枚举右边界,这样就将问题转化为 求区间和最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <iostream>

const int N = 105;
int arr[N][N], sum[N][N];

int n;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &arr[i][j]);
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + arr[i][j];
}
}

int ans = -1e9;
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 = std::max(last, 0) + sum[j][k] - sum[i - 1][k];
ans = std::max(ans, last);
}
}
}
printf("%d\n", ans);
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!