个人网站素材下载,深圳网站开发运营公司,上海专业网站制作公司,高端服装品牌排行榜【华为OD-E卷 - 最大矩阵和 100分#xff08;python、java、c、js、c#xff09;】
题目
给定一个二维整数矩阵#xff0c;要在这个矩阵中选出一个子矩阵#xff0c;使得这个子矩阵内所有的数字和尽量大#xff0c;我们把这个子矩阵称为和最大子矩阵#xff0c;子矩阵的…【华为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输出
20python解法
解题思路本代码的目标是在 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然后枚举下边界 ji ≤ 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)]# 计算一维数组的最大子数组和 (Kadanes 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];}// 在压缩后的数组上求最大子数组和Kadanes AlgorithmmaxSum Math.max(maxSum, kadane(colSum));}}return maxSum; // 返回最大子矩阵和}// 使用 Kadanes 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然后枚举下边界 bottomtop ≤ bottom rows。 使用 colSum[col] 存储 top 到 bottom 之间的列和将二维问题压缩为一维最大子数组和问题。 在 colSum 上调用 kadane(colSum) 计算最大子数组和。 返回 maxSum 作为最大子矩阵和
#include iostream
#include vector
#include climitsusing namespace std;// 使用 Kadanes Algorithm 计算一维数组的最大子数组和
int kadane(const vectorint 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 vectorvectorint grid, int rows, int cols) {int maxSum INT_MIN; // 记录最大子矩阵和// 枚举上边界 topfor (int top 0; top rows; top) {vectorint 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];}// 在压缩后的数组上求最大子数组和Kadanes AlgorithmmaxSum max(maxSum, kadane(colSum));}}return maxSum; // 返回最大子矩阵和
}int main() {int rows, cols;cin rows cols; // 读取矩阵的行数和列数// 读取矩阵数据vectorvectorint grid(rows, vectorint(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然后枚举下边界 bottomtop ≤ 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];}// 在压缩后的数组上求最大子数组和Kadanes AlgorithmmaxSum Math.max(maxSum, kadane(colSum));}}return maxSum; // 返回最大子矩阵和
}// 使用 Kadanes 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;
}
注意
如果发现代码有用例覆盖不到的情况欢迎反馈会在第一时间修正更新。 解题不易如对您有帮助欢迎点赞/收藏
