题目描述
给定一个包含整数的二维矩阵,子矩形是位于整个阵列内的任何大小为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。
算法1
暴力枚举
时间复杂度 O(n^4)
直接枚举每个矩阵的和,找出最大值。
其实按照时间复杂度感觉不能过,希望y总把数据加强一下,不然上课的解法就没什么意思了QVQ
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int a[N][N];
int f[N][N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ) cin >> a[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
int ans = -INF;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
for (int x = 1; x <= i; x ++ )
for (int y = 1; y <= j; y ++ )
ans = max(ans, f[i][j] - f[i][y - 1] - f[x - 1][j] + f[x - 1][y - 1]);
cout << ans << endl;
return 0;
}
= =暴力出奇迹。。。
乱搞就搞出来了。。