下面是一个2020的矩阵,矩阵中的每个数字是一个1到9之间的数字,请注意显示时去除了分隔符号。
69859241839387868941
17615876963131759284
37347348326627483485
53671256556167864743
16121686927432329479
13547413349962773447
27979945929848824687
53776983346838791379
56493421365365717745
21924379293872611382
93919353216243561277
54296144763969257788
96233972513794732933
81443494533129939975
61171882988877593499
61216868895721348522
55485345959294726896
32124963318242554922
13593647191934272696
56436895944919899246
矩阵中一个子矩阵的值是指子矩阵中所有数值的和。
请问,矩阵中值最大的一个55的子矩阵的值是多少?
二维前缀和,有帮助望采纳!
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main()
{
int n = 20, m = 20;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
}
}
//初始化前缀和数组
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int x = 0, y = 0;
vector<int> ans;
for (x = 1; x <= 16; x++)
{
for (y = 1; y <= 16; y++)
{
ans.push_back(s[x + 4][y + 4] - s[x + 4][y - 1] - s[x - 1][y + 4] + s[x - 1][y - 1]);
}
}
sort(ans.begin(), ans.end());
cout << ans[ans.size() - 1] << endl;
return 0;
}
可以讲清楚点嘛