A18845. 固定大小矩形最大和
填空题
较难
知识点
题目描述
固定大小矩形最大和
题目描述
给定一个n行m列的整数矩阵，求矩阵中所有2*2大小的子矩形的元素和的最大值。
输入格式
第一行两个整数n,m（2≤n,m≤100）
接下来n行，每行m个整数，代表矩阵元素
输出格式
输出一个整数，为所有2*2子矩形的最大和
样例输入
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16样例输出
58参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int a[N][N], sum[N][N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
// 预处理前缀和
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
int maxn = -1e9;
// 枚举所有2*2矩形右下角
for(int i = 2; i <= n; i++)
{
for(int j = 2; j <= m; j++)
{
// 2*2矩形左上角(i-1,j-1) 右下角(i,j)
int now = sum[i][j] - sum[i-2][j] - sum[i][j-2] + sum[i-2][j-2];
maxn = max(maxn, now);
}
}
cout << maxn << endl;
return 0;
}
上一题
下一题