当前位置：首页 > news >正文

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

news 来源：原创 2025/5/8 17:10:41

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

题目

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

输入描述

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

输出描述

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

用例

用例一：

输入：

输出：

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)

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

注意：

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

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

【华为OD-E卷 - 最大矩阵和 100分（python、java、c、js、c）】题目给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的…...

编程日记 2025/5/8 17:10:41

Mysql系列之--重新认识Mysql

1、Mysql是什么 Mysql是一个被广泛使用的开源的关系型数据库管理系统（RDBMS），使用结构化查询语句SQL进行管理和操作数据。Mysql有客户端和服务端，客户端通过ip地址、端口、用户名、密码连接到服务端，然后使用SQL语句进…...

编程日记 2025/5/9 15:12:19

利用UNIAPP实现短视频上下滑动播放功能

在 UniApp 中实现一个短视频上下滑动播放的功能，可以使用 swiper 组件来实现滑动效果，并结合 video 组件来播放短视频。以下是一个完整的示例，展示如何在 UniApp 中实现这一功能。 1. 创建 UniApp 项目如果你还没有创建 UniApp 项目，可以使用 HBuilderX 创建一个新的项目…...

编程日记 2025/5/7 5:42:29

计算机毕业设计hadoop+spark+hive民宿推荐系统酒店推荐系统民宿价格预测酒店价预测机器学习深度学习 Python爬虫 HDFS集群

温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 作者简介：Java领…...

编程日记 2025/5/8 20:42:03

Shell 中的 Globbing：原理、使用方法与实现解析（中英双语）

Shell 中的 Globbing：原理、使用方法与实现解析在 Unix Shell（如 Bash、Zsh）中，globbing 是指文件名模式匹配（filename pattern matching），它允许用户使用特殊的通配符（wildcards…...

编程日记 2025/5/9 14:44:30

解决 ssh connect to host github.com port 22 Connection timed out

一、问题描述本地 pull/push 推送代码到 github 项目报 22 端口连接超时，测试连接也是 22 端口连接超时 ssh 密钥没问题、也开了 Watt Toolkit 网络是通的，因此可以强制将端口切换为 443 二、解决方案 1、测试连接 ssh -T gitgithub.com意味着无法通…...

编程日记 2025/5/9 15:15:08

CSS的媒体查询语法

CSS的媒体查询语法常见的媒体类型常见的特性示例 CSS的媒体查询语法可以根据不同的设备特性（如屏幕尺寸、分辨率等）应用不同的样式。基本语法如下： media 媒体类型 and (特性: 值) {/* 样式规则 */ }常见的媒体类型 screen：用于…...

编程日记 2025/5/9 14:29:10

生产环境超实用shell脚本一

生产环境超实用shell脚本一 Shell脚本作为一种强大的自动化工具，能够帮助运维人员轻松应对各种复杂的任务。本文将为您介绍服务器健康检查、日志清理、备份以及监控等多个方面，并详细阐述每个脚本的功能和应用场景，助力您提升运维效率&…...

编程日记 2025/5/9 15:09:39

【1】高并发导出场景下，服务器性能瓶颈优化

高并发导出场景下，服务器性能瓶颈通常出现在 CPU、内存、磁盘 I/O 或网络带宽等方面。为了解决这些问题，可以从以下几个方面进行优化： 1. 优化导出逻辑减少计算复杂度：检查导出逻辑中是否存在不必要的计算或重复操作，…...

编程日记 2025/5/6 4:53:00

包含了sync.Mutex,sync.RWMutex,sync.Cond,sync.Map,sync.Once等demo sync.Mutex //讲解mutex import ("fmt""math/rand""sync""time" )type Toilet struct {m sync.Mutex } type Person struct {Name string }var DateTime "2…...

编程日记 2025/5/9 15:32:24

一文读懂：TCP网络拥塞的应对策略与方案

TCP（传输控制协议）是互联网中广泛使用的可靠传输协议，它通过序列号、确认应答、重发控制、连接管理以及窗口控制等机制确保数据的可靠传输。然而，在网络环境中，由于多个主机共享网络资源，网络拥塞成为了一个…...

编程日记 2025/5/7 7:00:20

用DeepSeek分析总结一下DeepSeek发表过的8篇论文

1. 《深度求索大语言模型：以长期主义拓展开源语言模型》（2024年1月5日） 2. 《深度求索代码模型：当大语言模型遇上编程——代码智能的崛起》（2024年1月26日） 3. 《深度求索视觉语言模型：迈向真…...

编程日记 2025/5/9 14:33:48

node.js使用mysql2对接数据库

一、引言在现代Web开发中，Node.js作为一种高效、轻量级的JavaScript运行时环境，已经广泛应用于后端服务的开发中。而MySQL，作为一个广泛使用的关系型数据库管理系统（RDBMS），提供了强大的数据存储和查询功能…...

编程日记 2025/5/9 15:30:24

华为支付-免密支付接入免密代扣说明

免密代扣包括支付并签约以及签约代扣场景。开发者接入免密支付前需先申请开通签约代扣产品（即申请配置免密代扣模板及协议模板ID）。华为支付以模板维度管理每一个代扣扣费服务，主要组成要素如下： 接入免密支付需注意&#x…...

编程日记 2025/5/5 11:10:48

Java 面试真题解析与技巧分享

Java 面试对于每一位 Java 开发者来说都是至关重要的，它不仅是对我们技术能力的检验，更是我们迈向理想工作岗位的关键一步。在面试中，掌握常见真题的解题思路和回答技巧，能够让我们更加自信地展示自己的实力。本文将结合具体的面试…...

编程日记 2025/5/4 12:25:12

使用 Python 编程语言来实现机器学习小项目教程案例

以下是一个简单的机器学习小项目教程案例，使用 Python 编程语言和 Scikit-learn 库来实现一个分类任务。我们将使用经典的鸢尾花（Iris）数据集来训练一个分类器，预测鸢尾花的种类。项目目标使用机器学习算法对鸢尾花数据集进行分类，预测鸢尾花的类别（Setosa、Versicolor…...

编程日记 2025/5/9 5:11:13

网络安全 | 零信任架构：重构安全防线的未来趋势

网络安全 | 零信任架构：重构安全防线的未来趋势一、前言二、零信任架构的核心概念与原理2.1 核心概念2.2 原理三、零信任架构的关键技术组件3.1 身份管理与认证系统3.2 授权与访问控制系统3.3 网络与安全监测系统3.4 加密与数据保护技术四、零信任架构与传统安全…...

编程日记 2025/5/9 15:20:42

react关于手搓antd pro面包屑的经验（写的不好请见谅）

我们先上代码，代码里面都有注释，我是单独写了一个组件，方便使用，在其他页面引入就行了还使用了官方的Breadcrumb组件 import React, { useEffect, useState } from react; import { Breadcrumb, Button } from antd; import { …...

编程日记 2025/5/9 15:06:18

PHP-运算符

[题目信息]： 题目名称题目难度PHP-运算符2 [题目考点]： PHP运算符优先级[Flag格式]: SangFor{zEk4r_djfgy0CibPz6LdXpwBrXRckhIT}[环境部署]： docker-compose.yml文件或者docker tar原始文件。 http://分配ip:2067[题目writeup]&#x…...

编程日记 2025/5/7 3:02:18

chrome浏览器chromedriver下载

chromedriver 下载地址 https://googlechromelabs.github.io/chrome-for-testing/ 上面的链接有和当前发布的chrome浏览器版本相近的chromedriver 实际使用感受 chrome浏览器会自动更新，可以去下载最新的chromedriver使用，自动化中使用新的chromedr…...

编程日记 2025/5/9 15:30:24

BurpSuite抓包与HTTP基础

文章目录前言一、BurpSuite1.BurpSuite简介2.BurpSuite安装教程(1)BurpSuite安装与激活(2)安装 https 证书 3.BurpSuite使用4.BurpSuite资料二、图解HTTP1.HTTP基础知识2.HTTP客户端请求消息3.HTTP服务端响应消息4.HTTP部分请求方法理解5.HTTPS与HTTP 总结前言在网络安全和…...

编程日记 2025/5/9 15:25:24

SQLAlchemy 2.0的简单使用教程

SQLAlchemy 2.0相比1.x进行了很大的更新，目前网上的教程不多，以下以链接mysql为例介绍一下基本的使用方法环境及依赖 Python:3.8 mysql:8.3 Flask:3.0.3 SQLAlchemy:2.0.37 PyMySQL:1.1.1使用步骤 1、创建引擎，链接到mysql engine crea…...

编程日记 2025/5/9 14:18:03

Android原生开发问题汇总

Fragment顶部出现一个白条怎么办？父类布局搞事情。 layer-list被拉伸问题 Android之 ImageView android:src和tools:src的区别是什么? Android运行时权限的总结，以及EasyPermissions框架的使用 Android Studio添加EasyPemissions Android中module怎…...

编程日记 2025/5/9 14:41:04

springboot中使用注解实现分布式锁

下面将详细介绍如何在 Spring Boot 里借助注解实现分布式锁，以login_lock:作为锁的 key 前缀，使用请求参数里的phone值作为 key，等待时间设为 0 秒，锁的持续时间为 10 秒。我们会使用 Redis 来实现分布式锁，同时借助 S…...

编程日记 2025/5/3 14:36:02

Android TabLayout 使用进阶（含源码）

android:layout_height“match_parent” android:orientation“vertical” tools:context“.mode2.ClassificationActivity”> <com.google.android.material.tabs.TabLayout android:id“id/tab_layout” android:layout_width“match_parent” android:layout_he…...

编程日记 2025/5/9 14:14:28

数据库系统概论的第六版与第五版的区别，附pdf

我用夸克网盘分享了「数据库系统概论第五六版资源」，点击链接即可保存。链接：https://pan.quark.cn/s/21a278378dee 第6版教材修订的主要内容为了保持科学性、先进性和实用性，在第5版教材基础上对全书内容进行了修改、更新和充实。在科…...

编程日记 2025/5/9 14:09:51

管理etcd的存储空间配额

如何管理etcd的存储空间配额 - 防止集群存储耗尽指南本文基于etcd v3.4官方文档编写为什么需要空间配额？ 在分布式系统中，etcd作为可靠的键值存储，很容易成为系统瓶颈。当遇到以下情况时： 应用程序频繁写入大量数据未及时清理…...

编程日记 2025/5/9 10:16:55

深入浅出 NRM：加速你的 npm 包管理之旅

文章目录前言一、NRM 是什么？二、为什么需要 NRM？三、NRM 的优势四、NRM 的安装与使用4.1 安装 NRM4.2 查看可用的 npm 源4.3 切换 npm 源4.4 测试 npm 源速度4.5 添加自定义 npm 源4.6 删除 npm 源五、NRM 的进阶使用六、总结前言作为一名 JavaScr…...

编程日记 2025/5/9 14:02:29

ESP32开发学习记录---》GPIO

she 2025年2月5日，新年后决定开始充电提升自己，故作此记,以前没有使用过IDF开发ESP32因此新年学习一下ESP32。 ESPIDF开发环境配置网上已经有很多的资料了，我就不再赘述，我这里只是对我的学习经历的一些记录。首先学习一个…...

编程日记 2025/5/8 20:07:17

stm32点灯 GPIO的输出模式

目录 1.选择RCC时钟 2.SYS 选择调试模式 SW 3.GPIO 配置 4.时钟树配置（ 默认不变）HSI 高速内部时钟8Mhz 5.项目配置 6.代码延时1s循环LED亮灭 1.选择RCC时钟 2.SYS 选择调试模式 SW 3.GPIO 配置 4.时钟树配置（ 默认不变&#xff09…...

编程日记 2025/5/9 13:45:43

[paddle] 矩阵的分解

特征值设 A A A 是一个 n n n \times n nn 的方阵， λ \lambda λ 是一个标量， v \mathbf{v} v 是一个非零向量。如果满足以下方程： A v λ v A\mathbf{v} \lambda\mathbf{v} Avλv 则称 λ \lambda λ 为矩阵 A A A 的一个特征值…...

编程日记 2025/5/4 17:30:58

【基于SprintBoot+Mybatis+Mysql】电脑商城项目之修改密码和个人资料

🧸安清h：个人主页 🎥个人专栏：【Spring篇】【计算机网络】【Mybatis篇】 🚦作者简介：一个有趣爱睡觉的intp，期待和更多人分享自己所学知识的真诚大学生。目录 🎃1.修改密码 -持久…...

编程日记 2025/5/6 8:57:30

【深度学习】DataLoader自定义数据集制作

第一步导包 import os import matplotlib.pyplot as plt %matplotlib inline import numpy as np import torch from torch import nn import torch.optim as optim import torchvision from torchvision import transforms,models,datasets import imageio import time impo…...

编程日记 2025/5/5 17:43:13

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

题目

输入描述

输出描述

用例

用例一：

输入：

输出：

python解法

java解法

C++解法

C解法

解题思路

JS解法

解题思路

注意：

相关文章：