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

news/2025/2/3 22:33:16 标签: 华为od, 矩阵, python, java, c++

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')  # 记录最大子矩阵和

    # 遍历所有可能的上边界 i
    for i in range(n):
        compressed = [0] * m  # 用于存储列压缩的数组

        # 遍历所有可能的下边界 j
        for 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;

        // 枚举上边界 top
        for (int top = 0; top < rows; top++) {
            int[] colSum = new int[cols]; // 列压缩数组，存储 top 到 bottom 之间的列和

            // 枚举下边界 bottom
            for (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; // 记录最大子矩阵和

    // 枚举上边界 top
    for (int top = 0; top < rows; top++) {
        vector<int> colSum(cols, 0); // 列压缩数组，存储 top 到 bottom 之间的列和

        // 枚举下边界 bottom
        for (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 {
        // 读取矩阵数据，并存入 inputData
        inputData.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; // 记录最大子矩阵和

    // 枚举上边界 top
    for (let top = 0; top < rows; top++) {
        let colSum = new Array(cols).fill(0); // 列压缩数组，存储 top 到 bottom 之间的列和

        // 枚举下边界 bottom
        for (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.niftyadmin.cn/n/5841077.html

相关文章

uv 安装包

uv 安装包

是的&#xff0c;你可以使用 uv 来安装 Python 包。uv 是一个高性能的 Python 包安装器和解析器&#xff0c;由 astral.sh 团队开发&#xff0c;旨在替代 pip 和 pip-tools&#xff0c;提供更快的包安装体验。 ### 如何使用 uv 安装包 1. **安装 uv**&#xff1a; 如果你还…
阅读更多...
穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞单词搜索

穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞单词搜索

题解如下 题目&#xff1a;解析决策树&#xff1a;代码设计&#xff1a; 代码&#xff1a; 题目&#xff1a; 解析 决策树&#xff1a; 代码设计&#xff1a; 代码&#xff1a; class Solution {private boolean[][] visit;//标记使用过的数据int m,n;//行&#xff0c;列char…
阅读更多...
MySQL的GROUP BY与COUNT()函数的使用问题

MySQL的GROUP BY与COUNT()函数的使用问题

在MySQL中&#xff0c;GROUP BY和 COUNT()函数是数据聚合查询中非常重要的工具。正确使用它们可以有效地统计和分析数据。然而&#xff0c;不当的使用可能会导致查询结果不准确或性能低下。本文将详细讨论 GROUP BY和 COUNT()函数的使用方法及常见问题&#xff0c;并提供相应的…
阅读更多...
【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】2.6 广播机制核心算法：维度扩展的数学建模

【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】2.6 广播机制核心算法：维度扩展的数学建模

2.6 广播机制核心算法&#xff1a;维度扩展的数学建模 目录/提纲 #mermaid-svg-IfELXmhcsdH1tW69 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-IfELXmhcsdH1tW69 .error-icon{fill:#552222;}#mermaid-svg-IfELXm…
阅读更多...
ELECTRA：作为判别器而非生成器的预训练文本编码器

ELECTRA：作为判别器而非生成器的预训练文本编码器

摘要 诸如BERT之类的掩码语言建模&#xff08;MLM&#xff09;预训练方法通过将某些标记替换为[MASK]来破坏输入&#xff0c;然后训练模型以重建原始标记。尽管这些方法在下游自然语言处理&#xff08;NLP&#xff09;任务中表现良好&#xff0c;但它们通常需要大量的计算资源…
阅读更多...
DeepSeek R1 简易指南：架构、本地部署和硬件要求

DeepSeek R1 简易指南：架构、本地部署和硬件要求

DeepSeek 团队近期发布的DeepSeek-R1技术论文展示了其在增强大语言模型推理能力方面的创新实践。该研究突破性地采用强化学习&#xff08;Reinforcement Learning&#xff09;作为核心训练范式&#xff0c;在不依赖大规模监督微调的前提下显著提升了模型的复杂问题求解能力。 技…
阅读更多...
动手学图神经网络（8）：在消息传递中定制聚合操作

动手学图神经网络（8）：在消息传递中定制聚合操作

在消息传递中定制聚合操作 安装Pytorch和PyG # 安装所需的包 import os import torch os.environ[TORCH] = torch.__version__# 以下是安装命令，实际运行时可取消注释 #!pip install -q torch-scatter -f https://data.pyg.org/whl/torch-${TORCH}.html #!pip install -q to…
阅读更多...
14 2D矩形模块（ rect.rs）

14 2D矩形模块（ rect.rs）

一、 rect.rs源码 // Copyright 2013 The Servo Project Developers. See the COPYRIGHT // file at the top-level directory of this distribution. // // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or // http://www.apache.org/licenses/LICENS…
阅读更多...
最新文章

Copyright @ 2022~2023