import java.util.*;
import java.io.*;
public class Main {
private static int N = 110;
private static int[][] arr = new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 前缀和
for (int i = 1; i <= n ; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = sc.nextInt();
arr[i][j] += arr[i-1][j];
}
}
int ans = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
int num = 0;
for (int k = 1; k <= n; k++) {
num = Math.max(num, 0) + arr[j][k] - arr[i-1][k];
ans = Math.max(ans, num);
}
}
}
System.out.println(ans);
sc.close();
}
}
用一个直观点的图结合y总的视频来理解会更好
- 这里可以把第三层for循环里的东西先看做一个一维的处理连续子数组最大和。
num = Math.max(num,0) + x
- 然后把后面那个一维的x拿出来细看,其实代表的是二维数组,那么我们可以看到绿色的部分就是我们要求的和,红色的减去蓝色的部分就能得到绿色的部分差值了