【问题描述】
下面是一个20*20的矩阵,矩阵中的每个数字是一个1到9之间的数字,请注意显示时去除了分隔符号。
矩阵中一个子矩阵的值是指子矩阵中所有数值的和。
请问,矩阵中值最大的一个 5 * 5 的子矩阵的值是多少?
样例
69859241839387868941
17615876963131759284
37347348326627483485
53671256556167864743
16121686927432329479
13547413349962773447
27979945929848824687
53776983346838791379
56493421365365717745
21924379293872611382
93919353216243561277
54296144763969257788
96233972513794732933
81443494533129939975
61171882988877593499
61216868895721348522
55485345959294726896
32124963318242554922
13593647191934272696
56436895944919899246
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int s[N][N],ans;
int get_sum(int x,int y)
{
return s[x][y] - s[x - 5][y] - s[x][y - 5] + s[x - 5][y - 5];
}
int main()
{
int n = 20;
for(int i = 1;i <= n ; i ++)
{
string a;
cin >> a;
for(int j = 1; j <= n; j ++)
s[i + 1][j + 1] = a[j] - '0' + s[i + 1][j] + s[i][j + 1] - s[i][j];
}
for(int i = 5; i < n ; i ++)
for(int j = 5;j < n;j ++)
{
ans = max(ans,get_sum(i,j));
}
cout << ans << endl;
return 0;
}