蓝桥杯最大子阵Java
时间: 2024-02-23 20:41:32 浏览: 23
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 矩阵的行数
int m = scanner.nextInt(); // 矩阵的列数
int[][] matrix = new int[n][m]; // 矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = scanner.nextInt();
}
}
int max = Integer.MIN_VALUE; // 最大子阵的和
for (int i = 0; i < n; i++) {
int[] sum = new int[m]; // 存放每一列的和
for (int j = i; j < n; j++) {
int curSum = 0; // 当前子阵的和
for (int k = 0; k < m; k++) {
sum[k] += matrix[j][k]; // 更新每一列的和
curSum += sum[k]; // 计算当前子阵的和
if (curSum > max) {
max = curSum; // 更新最大子阵的和
}
if (curSum < 0) {
curSum = 0; // 如果当前子阵的和小于0,就抛弃它
}
}
}
}
System.out.println(max);
}
}