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

server/2025/2/5 13:15:38/

pythonjavacjsc_0">【华为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_37">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 作为最大子矩阵和

python"># 读取矩阵的行数(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_99">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 作为最大子矩阵和

java">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 作为最大子矩阵和

javascript">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;
}

注意：

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


http://www.ppmy.cn/server/165152.html

相关文章

搜索引擎友好：设计快速收录的网站架构

搜索引擎友好：设计快速收录的网站架构

本文来自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/14.html 为了设计一个搜索引擎友好的网站架构&#xff0c;以实现快速收录&#xff0c;可以从以下几个方面入手&#xff1a; 一、清晰的目录结构与层级 合理划分内容&#xff1a;目录结构应…
阅读更多...
计算机网络 IP 网络层 2 （重置版）

计算机网络 IP 网络层 2 （重置版）

IP的简介&#xff1a; IP 地址是互联网协议地址&#xff08;Internet Protocol Address&#xff09;的简称&#xff0c;是分配给连接到互联网的设备的唯一标识符&#xff0c;用于在网络中定位和通信。 IP编制的历史阶段&#xff1a; 1&#xff0c;分类的IP地址&#xff1a; …
阅读更多...
Brave132 编译指南 Windows 篇：配置 Git（四）

Brave132 编译指南 Windows 篇：配置 Git（四）

1. 引言 在 Brave 浏览器 132 版本的开发流程中&#xff0c;Git 作为核心的版本控制工具&#xff0c;发挥着至关重要的作用。作为业界主流的分布式版本控制系统&#xff0c;Git 为开发者提供了强大的源代码管理能力。借助 Git&#xff0c;您可以轻松追踪代码的每一次变更、管理…
阅读更多...
解决国内服务器 npm install 卡住的问题

解决国内服务器 npm install 卡住的问题

在使用国内云服务器时&#xff0c;经常会遇到 npm install 命令执行卡住的情况。本文将分享一个典型案例以及常见的解决方案。 问题描述 在执行以下命令时&#xff1a; mkdir test-npm cd test-npm npm init -y npm install lodash --verbose安装过程会卡在这个状态&#xf…
阅读更多...
Vue模板语法与常用指令深度解析

Vue模板语法与常用指令深度解析

Vue模板语法与常用指令深度解析 Vue模板语法与常用指令深度解析一、Vue模板语法基础1.1 插值语法1.2 JavaScript表达式 二、核心指令深度解析2.1 条件渲染&#xff1a;v-if 家族指令2.1.1 基础用法与原理2.1.2 v-if vs v-show 深度对比2.1.3 高级用法模式2.1.4 性能优化指南 2.…
阅读更多...
2025国自然青年科学基金项目B类答辩PPT制作案例模板

2025国自然青年科学基金项目B类答辩PPT制作案例模板

2025 年度国家自然科学基金项目申请指南发布后&#xff0c;更新了各项目的撰写提纲及相关要求。将国家杰出青年科学基金项目更名为青年科学基金项目&#xff08;A 类&#xff09;&#xff0c;将优秀青年科学基金项目更名为青年科学基金项目&#xff08;B 类&#xff09;&#x…
阅读更多...
蓝桥杯模拟算法：蛇形方阵

蓝桥杯模拟算法：蛇形方阵

P5731 【深基5.习6】蛇形方阵 - 洛谷 | 计算机科学教育新生态 我们只要定义两个方向向量数组&#xff0c;这种问题就可以迎刃而解了 比如我们是4的话&#xff0c;我们从左向右开始存&#xff0c;1&#xff0c;2&#xff0c;3&#xff0c;4 到5的时候y就大于4了就是越界了&…
阅读更多...
Rust 语言入门

Rust 语言入门

文章来源&#xff1a;Rust 编程语言 -- Rust教程|Rust中文文档|Rust编程|Rust官方文档 安装 第一步是安装 Rust。我们将通过 下载 Rust&#xff0c;一个 用于管理 Rust 版本和相关工具的命令行工具。您将需要 用于下载的 Internet 连接。rustup 注意&#xff1a; 如果你出于…
阅读更多...
最新文章

Copyright @ 2022~2023