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

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为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
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
输出：
20
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1

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

    # 遍历所有可能的上边界 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))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

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;

        // 枚举上边界 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;
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

解题步骤
读取输入

读取 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 
#include 
#include 

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

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

解题步骤
读取输入

读取 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 {
        // 读取矩阵数据，并存入 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;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

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

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145184699"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！