【华为OD-E卷 - 108 最大矩阵和 100分（python、java、c++、js、c）】

【华为OD-E卷 - 最大矩阵和 100分（python、java、c++、js、c）】

题目

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

输入描述

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

输出描述

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

用例

用例一：

输入：

3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3

输出：

20

python解法

• 解题思路：
• 本代码的目标是在 n x m 的二维矩阵中找到最大子矩阵的和。
  该问题可以通过**Kadane’s Algorithm（卡丹算法）**优化解决。

解题步骤
输入处理：

读取 n 和 m，表示矩阵的行数和列数。
读取 n 行 m 列的矩阵，存入 grid。
最大子数组和 maxSumSubarray(arr)：

该函数使用Kadane’s Algorithm 在一维数组 arr 上计算最大连续子数组和。
通过遍历 arr，维护当前最大子数组和 (curr_sum) 和 全局最大 (max_sum)。
枚举上下边界，计算最大子矩阵和 findMaxMatrixSum(matrix)：

固定上边界 i，然后枚举下边界 j（i ≤ j < n）。
使用 compressed[k] 存储 i 到 j 之间的列和，将二维问题压缩为一维最大子数组和问题。
在 compressed 上调用 maxSumSubarray(compressed) 计算最大和。
返回 max_sum 作为最大子矩阵和

# 读取矩阵的行数(n) 和 列数(m)
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]# 计算一维数组的最大子数组和 (Kadane's Algorithm)
def maxSumSubarray(arr):max_sum = arr[0]  # 记录全局最大子数组和curr_sum = arr[0] # 记录当前子数组和# 遍历数组，计算最大连续子数组和for val in arr[1:]:curr_sum = max(val, curr_sum + val)  # 选择是否包含之前的子数组max_sum = max(max_sum, curr_sum)  # 更新最大和return max_sum# 计算矩阵中的最大子矩阵和
def findMaxMatrixSum(matrix):max_sum = -float('inf')  # 记录最大子矩阵和# 遍历所有可能的上边界 ifor i in range(n):compressed = [0] * m  # 用于存储列压缩的数组# 遍历所有可能的下边界 jfor j in range(i, n):# 计算当前列的前缀和for k in range(m):compressed[k] += matrix[j][k]# 在压缩后的数组上求最大子数组和max_sum = max(max_sum, maxSumSubarray(compressed))return max_sum# 输出最大子矩阵和
print(findMaxMatrixSum(grid))

java解法

• 解题思路
• 本代码的目标是在 rows x cols 的二维矩阵中找到最大子矩阵的和。
  采用 Kadane’s Algorithm（卡丹算法） 进行优化计算。

解题步骤
读取输入

读取 rows 和 cols，表示矩阵的行数和列数。
读取 rows × cols 的矩阵，并存入 grid。
压缩行并使用 Kadane’s Algorithm 求最大子数组和

遍历所有可能的上边界 top，并向下扩展到下边界 bottom。
维护一个 colSum 数组，存储 top 到 bottom 之间的列和，将二维问题转换为一维最大子数组和问题。
在 colSum 上应用 Kadane’s Algorithm 计算最大子数组和。
返回 maxSum 作为最大子矩阵和

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);// 读取矩阵的行数(rows) 和 列数(cols)int rows = input.nextInt();int cols = input.nextInt();// 读取矩阵数据int[][] grid = new int[rows][cols];for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {grid[i][j] = input.nextInt();}}// 计算并输出最大子矩阵和System.out.println(findMaxSum(grid, rows, cols));}// 计算二维矩阵中的最大子矩阵和public static int findMaxSum(int[][] grid, int rows, int cols) {int maxSum = Integer.MIN_VALUE;// 枚举上边界 topfor (int top = 0; top < rows; top++) {int[] colSum = new int[cols]; // 列压缩数组，存储 top 到 bottom 之间的列和// 枚举下边界 bottomfor (int bottom = top; bottom < rows; bottom++) {// 计算 top 到 bottom 之间的列和for (int col = 0; col < cols; col++) {colSum[col] += grid[bottom][col];}// 在压缩后的数组上求最大子数组和（Kadane's Algorithm）maxSum = Math.max(maxSum, kadane(colSum));}}return maxSum; // 返回最大子矩阵和}// 使用 Kadane's Algorithm 计算一维数组的最大子数组和private static int kadane(int[] arr) {int maxCurrent = arr[0], maxGlobal = arr[0];// 遍历数组，计算最大连续子数组和for (int i = 1; i < arr.length; i++) {maxCurrent = Math.max(arr[i], maxCurrent + arr[i]); // 选择是否包含之前的子数组maxGlobal = Math.max(maxGlobal, maxCurrent); // 更新最大和}return maxGlobal;}
}

C++解法

• 解题思路
• 本代码的目标是在 rows × cols 的二维矩阵中找到最大子矩阵的和，使用 Kadane’s Algorithm（卡丹算法） 进行优化计算。

解题步骤
读取输入

读取 rows 和 cols，表示矩阵的行数和列数。
读取 rows × cols 的矩阵，并存入 grid。
Kadane’s Algorithm 求最大子数组和 kadane(arr)

计算一维数组 arr 上的最大连续子数组和，用于处理列压缩后的一维问题。
枚举上下边界，计算最大子矩阵和 findMaxSum(grid, rows, cols)

固定上边界 top，然后枚举下边界 bottom（top ≤ bottom < rows）。
使用 colSum[col] 存储 top 到 bottom 之间的列和，将二维问题压缩为一维最大子数组和问题。
在 colSum 上调用 kadane(colSum) 计算最大子数组和。
返回 maxSum 作为最大子矩阵和

#include <iostream>
#include <vector>
#include <climits>using namespace std;// 使用 Kadane's Algorithm 计算一维数组的最大子数组和
int kadane(const vector<int>& arr) {int maxCurrent = arr[0]; // 当前子数组的最大和int maxGlobal = arr[0];  // 记录全局最大子数组和// 遍历数组，计算最大连续子数组和for (int i = 1; i < arr.size(); i++) {maxCurrent = max(arr[i], maxCurrent + arr[i]); // 选择是否包含之前的子数组maxGlobal = max(maxGlobal, maxCurrent); // 更新最大和}return maxGlobal;
}// 计算二维矩阵中的最大子矩阵和
int findMaxSum(const vector<vector<int>>& grid, int rows, int cols) {int maxSum = INT_MIN; // 记录最大子矩阵和// 枚举上边界 topfor (int top = 0; top < rows; top++) {vector<int> colSum(cols, 0); // 列压缩数组，存储 top 到 bottom 之间的列和// 枚举下边界 bottomfor (int bottom = top; bottom < rows; bottom++) {// 计算 top 到 bottom 之间的列和for (int col = 0; col < cols; col++) {colSum[col] += grid[bottom][col];}// 在压缩后的数组上求最大子数组和（Kadane's Algorithm）maxSum = max(maxSum, kadane(colSum));}}return maxSum; // 返回最大子矩阵和
}int main() {int rows, cols;cin >> rows >> cols; // 读取矩阵的行数和列数// 读取矩阵数据vector<vector<int>> grid(rows, vector<int>(cols));for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {cin >> grid[i][j];}}// 计算并输出最大子矩阵和cout << findMaxSum(grid, rows, cols) << endl;return 0;
}

C解法

• 解题思路

更新中

JS解法

• 解题思路

• 本代码的目标是在 rows × cols 的二维矩阵中找到最大子矩阵的和，采用 Kadane’s Algorithm（卡丹算法） 进行优化计算。

解题步骤
读取输入

读取 rows 和 cols，表示矩阵的行数和列数。
读取 rows × cols 的矩阵，并存入 inputData 数组。
当 inputData.length === rows 时，调用 findMaxSum(grid, rows, cols) 计算最大子矩阵和。
Kadane’s Algorithm 求最大子数组和 kadane(arr)

计算一维数组 arr 上的最大连续子数组和，用于处理列压缩后的一维问题。
枚举上下边界，计算最大子矩阵和 findMaxSum(grid, rows, cols)

固定上边界 top，然后枚举下边界 bottom（top ≤ bottom < rows）。
使用 colSum[col] 存储 top 到 bottom 之间的列和，将二维问题压缩为一维最大子数组和问题。
在 colSum 上调用 kadane(colSum) 计算最大子数组和。
返回 maxSum 作为最大子矩阵和

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let inputData = [];
let rows, cols;// 监听输入，每次读取一行
rl.on('line', (line) => {if (rows === undefined && cols === undefined) {// 读取第一行输入，获取矩阵的行数 (rows) 和列数 (cols)[rows, cols] = line.split(' ').map(Number);} else {// 读取矩阵数据，并存入 inputDatainputData.push(line.split(' ').map(Number));// 当所有行读取完毕时，计算最大子矩阵和if (inputData.length === rows) {const maxSum = findMaxSum(inputData, rows, cols);console.log(maxSum);rl.close();}}
});// 计算二维矩阵中的最大子矩阵和
function findMaxSum(grid, rows, cols) {let maxSum = Number.MIN_SAFE_INTEGER; // 记录最大子矩阵和// 枚举上边界 topfor (let top = 0; top < rows; top++) {let colSum = new Array(cols).fill(0); // 列压缩数组，存储 top 到 bottom 之间的列和// 枚举下边界 bottomfor (let bottom = top; bottom < rows; bottom++) {// 计算 top 到 bottom 之间的列和for (let col = 0; col < cols; col++) {colSum[col] += grid[bottom][col];}// 在压缩后的数组上求最大子数组和（Kadane's Algorithm）maxSum = Math.max(maxSum, kadane(colSum));}}return maxSum; // 返回最大子矩阵和
}// 使用 Kadane's Algorithm 计算一维数组的最大子数组和
function kadane(arr) {let maxCurrent = arr[0]; // 当前子数组的最大和let maxGlobal = arr[0];  // 记录全局最大子数组和// 遍历数组，计算最大连续子数组和for (let i = 1; i < arr.length; i++) {maxCurrent = Math.max(arr[i], maxCurrent + arr[i]); // 选择是否包含之前的子数组maxGlobal = Math.max(maxGlobal, maxCurrent); // 更新最大和}return maxGlobal;
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏