最大矩阵和
标题：最大矩阵和 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。
n, m = map(int, input().split()) matrix = [] for i in range(n): nums = list(map(int, input().split())) matrix.append(nums) ans = -1000 for i in range(n): b = [0]* m for j in range(i,n): sum = 0 for k in range(m): b[k] += matrix[j][k] if sum > 0: sum += b[k] else: sum = b[k] if sum>ans: ans = sum print(ans)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int m, n, i, j;
int a[][] = new int[10][10];
int sum[][] = new int[10][10];
int max;
int li, lj, ri, rj;
int temp = 0;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
a[i][j] = scanner.nextInt();
}
}
max = a[0][0];
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
sum[i][j] = a[i][j];
if (i != 0) {
sum[i][j] += sum[i - 1][j];
}
if (j != 0) {
sum[i][j] += sum[i][j - 1];
}
if (i != 0 && j != 0) {
sum[i][j] -= sum[i - 1][j - 1];
}
}
}
for (li = 0; li < n; li++) {
for (lj = 0; lj < m; lj++) {
for (ri = li; ri < n; ri++) {
for (rj = lj; rj < m; rj++) {
temp = sum[ri][rj];
if (li != 0) {
temp -= sum[li - 1][rj];
}
if (lj != 0) {
temp -= sum[ri][lj - 1];
}
if (li != 0 && lj != 0) {
temp += sum[li - 1][lj - 1];
}
if (temp > max) {
max = temp;
}
}
}
}
}
System.out.println(max);
}
}