【问题描述】
下面是一个20*20的矩阵，矩阵中的每个数字是一个1到9之间的数字，请注意显示时去除了分隔符号。
69859241839387868941
17615876963131759284
37347348326627483485
53671256556167864743
16121686927432329479
13547413349962773447
27979945929848824687
53776983346838791379
56493421365365717745
21924379293872611382
93919353216243561277
54296144763969257788
96233972513794732933
81443494533129939975
61171882988877593499
61216868895721348522
55485345959294726896
32124963318242554922
13593647191934272696
56436895944919899246
矩阵中一个子矩阵的值是指子矩阵中所有数值的和。
请问，矩阵中值最大的一个 5 * 5 的子矩阵的值是多少？
开始解题：做这个题想要快快地话可以使用二维前缀和求解。先把这个矩阵的二维前缀和数组sum求出来，再利用sum数组求每一个5*5矩阵的和，怎么求5*5呢？右下-（左下-1）-（右上-1）+（左上-1）哈哈哈，你去学会二维前缀和就知道我在说什么了。b站的二维前缀和教学视频
反正我就是看这个视频学会了前缀和与差分，学完之后做矩阵这个题真的是很好的练习题。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//方便操作，扩大一行一列，要不然下面-5那里会越界
int[][] a = new int[21][21];
for (int i = 1; i < 21; i++) {
String s = in.next();
for (int j = 1; j < 21; j++)
a[i][j] = s.charAt(i - 1) - '0';
}
int[][] sum = new int[21][21];
//初始化前缀和数组的第一行第一列
sum[0][0] = a[0][0];
for (int i = 1; i < 21; i++) {
sum[0][i] = sum[0][i - 1] + a[0][i];
sum[i][0] = sum[i - 1][0] + a[i][0];
}
//生成前缀和数组
for (int i = 1; i < 21; i++)
for (int j = 1; j < 21; j++)
sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
//开始找5×5矩阵的最大值啦
int max = Integer.MIN_VALUE, sum0;
for (int i = 5; i < 21; i++)
for (int j = 5; j < 21; j++) {
sum0 = sum[i][j] - sum[i][j - 5] - sum[i - 5][j] + sum[i - 5][j - 5];
if (max < sum0)
max = sum0;
}
System.out.println(max);
}
}
看完代码之后，相比暴力的嵌套4个for循环是不是快很多呢？
