题目描述
给定一个包含整数的二维矩阵,子矩形是位于整个阵列内的任何大小为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
利用一维求子序列最大和思想将二维序列转化
首先分析求一维子序列过程
状态分析:f[i] 表示前 i 个序列中最大子序列的和
状态计算:f[i] = max (a[i], f[i - 1] + a[i]) 分析前 i - 1 个是否可加 f[i - 1] < 0 则取 a[i] 作为当前最大的子序列和
C++ 代码
#include<iostream>
using namespace std;
const int N = 110;
int n;
int f[N], a[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
f[i] = max(a[i], f[i - 1] + a[i]);
cout << f[n] << endl;
return 0;
}
时间复杂度 $O(n)$
参考文献 y总代码
(求前缀和、dp)
二维同理
a[k] 存储第 k 列的值;
g[k] 记录当前所求得的序列中子序列的最大和
res 存储最大和的数值
C++ 代码
#include<iostream>
#include<limits.h>
using namespace std;
const int N = 110;
int n, res = INT_MIN;
int f[N][N];
int a[N], g[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
cin >> f[i][j];
f[i][j] += f[i - 1][j];
}
for(int i = 1; i <= n; i ++)
for(int j = i; j <= n; j ++)
{
for(int k = 1;k <= n; k ++)
{
a[k] = f[j][k] - f[i - 1][k];
g[k] = max(a[k], g[k - 1] + a[k]);
res = max(res, g[k]);
}
}
cout << res << endl;
return 0;
}