b√最大矩阵和

题目描述

给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵.
使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵
子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。

输入描述

输入的第一行包含2个整数n,m(1<= n,m<= 10)，表示一个n行m列的矩阵，下面有n行，每行有m个整数，同一行中，每2个数字之间有1个空格，最后一个数字后面没有空格，所有的数字的在[-1000,1000]之间。

输出描述

输出一行一个数字，表示选出的和最大子矩阵内所有的数字和。

用例

我也不会,以下思路源于这个文章最大矩阵和-CSDN博客和LeetCode - 53 最大子数组和_最大长度为质数的子数组和-CSDN博客

public class 最大矩阵和Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] matrix = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = sc.nextInt();}}int ans = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {ans = Math.max(ans, maxSubArraySum(matrix[i])); // 单行(第i行)子矩阵最大和for (int j = i + 1; j < n; j++) { // 将第 i+1 ~ n-1 行依次合并入第 i 行for (int k = 0; k < m; k++) {  // 矩阵压缩matrix[i][k] += matrix[j][k];}ans = Math.max(ans, maxSubArraySum(matrix[i])); // 多行子矩阵最大和}}System.out.println(ans);}// 最大子数组和求解public static int maxSubArraySum(int[] nums) {int dp = nums[0];int res = dp;for (int i = 1; i < nums.length; i++) {dp = Math.max(dp, 0) + nums[i];res = Math.max(res, dp);}return res;}
}