\(AcWing\) \(126\). 最大的和
关键字
最大子段和，有一维和二维两种情况
一维：\(O(N)\)
二维：\(O(n^3)\)
一、题目描述
给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 \(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\)，表示方形二维数组的大小。
从第二行开始，输入由空格和换行符隔开的 \(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
二、一维情况
测试用例
7
5 -2 -4 8 -1 5 4
输出
16
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 110;
int a[N], s[N];
int f[N];
/*
7
5 -2 -4 8 -1 5 4
输出：
16
*/
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i]; // 累加出前缀和
}
int res = -INF;
for (int i = 1; i <= n; i++) {
f[i] = max(f[i - 1], 0) + a[i];
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
三、二维情况
左上角和右下角两个点可以确定一个矩形。枚举这两个点要用\(4\)个\(for\)循环 如果 用二维前缀和优化，那么这个做法的复杂度的就是\(O(n^4)\)。
其实这个方案可以优化，那就是 不枚举点。
所以我们可以 利用前缀和数组表示出每个色块表示的值，然后做类似找一维数组最大连续和的操作。这样来 枚举出最优矩形。
枚举边界要用\(3\)个\(for\)，复杂度为 \(O(n^3)\)
\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 110;
int g[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> g[i][j];
// 累加出并记录同一列的前缀和
g[i][j] += g[i - 1][j];
}
int res = -INF;
// 枚举边界1，2
for (int i = 1; i <= n; i++) // 起始行
for (int j = i; j <= n; j++) { // 终止行
// 枚举边界p
int last = 0;
for (int k = 1; k <= n; k++) {
last = max(last, 0) + g[j][k] - g[i - 1][k];
res = max(res, last);
}
}
cout << res << endl;
return 0;
}