【社招+校招】华为OD机试 - 最大矩阵和（Java、JavaScript、Python 和 C/C++）
【摘要】 鱼弦：公众号【红尘灯塔】，CSDN博客专家、内容合伙人、新星导师、全栈领域优质创作者 、51CTO(Top红人+专家博主) 、github开源爱好者（go-zero源码二次开发、游戏后端架构 https://github.com/Peakchen）最大矩阵和（Java、JavaScript、Python 和 C/C++）算法实现问题描述:在一个二维矩阵中，找到一个子矩阵，使得该子矩阵的元素...
鱼弦：公众号【红尘灯塔】，CSDN博客专家、内容合伙人、新星导师、全栈领域优质创作者 、51CTO(Top红人+专家博主) 、github开源爱好者（go-zero源码二次开发、游戏后端架构 https://github.com/Peakchen）
最大矩阵和（Java、JavaScript、Python 和 C/C++）
算法实现
问题描述:
在一个二维矩阵中，找到一个子矩阵，使得该子矩阵的元素之和最大。
解决方案:
- 动态规划法：
- 定义
dp[i][j]表示以左上角元素为 (1, 1)，右下角元素为 (i, j) 的子矩阵的最大和。 - 初始化
dp[i][j]为 0 或矩阵中元素的最小值。 - 递推计算
dp[i][j]：dp[i][j] = max(dp[i-1][j], dp[i][j-1] + matrix[i][j])dp[i][j] = max(dp[i][j], dp[i-1][j-1] + matrix[i][j])
- 找到
dp矩阵中的最大值，该值就是最大子矩阵的和。
- 定义
代码实现:
Java:
public class MaxMatrixSum {
public static int maxMatrixSum(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols];
// Initialize first row and first column
for (int i = 0; i < rows; i++) {
dp[i][0] = matrix[i][0];
}
for (int j = 0; j < cols; j++) {
dp[0][j] = matrix[0][j];
}
// Fill the rest of the dp table
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1] + matrix[i][j]);
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
}
}
// Find the maximum sum in the dp table
int maxSum = dp[0][0];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maxSum = Math.max(maxSum, dp[i][j]);
}
}
return maxSum;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, -3},
{4, 5, 6},
{7, 8, 9}
};
int maxSum = maxMatrixSum(matrix);
System.out.println("Maximum matrix sum: " + maxSum);
}
}
JavaScript:
function maxMatrixSum(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const dp = new Array(rows).fill(0).map(row => new Array(cols).fill(0));
// Initialize first row and first column
for (let i = 0; i < rows; i++) {
dp[i][0] = matrix[i][0];
}
for (let j = 0; j < cols; j++) {
dp[0][j] = matrix[0][j];
}
// Fill the rest of the dp table
for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1] + matrix[i][j]);
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
}
}
// Find the maximum sum in the dp table
let maxSum = dp[0][0];
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
maxSum = Math.max(maxSum, dpPython:
def max_matrix_sum(matrix):
rows = len(matrix)
cols = len(matrix[0])
dp = [[0 for _ in range(cols)] for _ in range(rows)]
# Initialize first row and first column
for i in range(rows):
dp[i][0] = matrix[i][0]
for j in range(cols):
dp[0][j] = matrix[0][j]
# Fill the rest of the dp table
for i in range(1, rows):
for j in range(1, cols):
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + matrix[i][j])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + matrix[i][j])
# Find the maximum sum in the dp table
max_sum = dp[0][0]
for i in range(rows):
for j in range(cols):
max_sum = max(max_sum, dp[i][j])
return max_sum
if __name__ == "__main__":
matrix = [
[1, 2, -3],
[4, 5, 6],
[7, 8, 9]
]
max_sum = max_matrix_sum(matrix)
print(f"Maximum matrix sum: {max_sum}")
C:
#include <stdio.h>
#include <stdlib.h>
int maxMatrixSum(int matrix[][100], int rows, int cols) {
int dp[rows][cols];
// Initialize first row and first column
for (int i = 0; i < rows; i++) {
dp[i][0] = matrix[i][0];
}
for (int j = 0; j < cols; j++) {
dp[0][j] = matrix[0][j];
}
// Fill the rest of the dp table
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + matrix[i][j]);
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
}
}
// Find the maximum sum in the dp table
int maxSum = dp[0][0];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maxSum = max(maxSum, dp[i][j]);
}
}
return maxSum;
}
int main() {
int matrix[][100] = {
{1, 2, -3},
{4, 5, 6},
{7, 8, 9}
};
int rows = 3;
int cols = 3;
int maxSum = maxMatrixSum(matrix, rows, cols);
printf("Maximum matrix sum: %d\n", maxSum);
return 0;
}
解释:
- Java 代码：
- 使用二维数组
dp来存储子矩阵的最大和。 - 初始化
dp数组的第一行和第一列。 - 使用递推公式计算
dp[i][j]的值。 - 遍历
dp数组找到最大值。
- 使用二维数组
- JavaScript 代码：
- 使用二维数组
dp来存储子矩阵的最大和。 - 初始化
dp数组的第一行和第一列。 - 使用递推公式计算
dp[i][j]的值。 - 遍历
dp数组找到最大值。
- 使用二维数组
- Python 代码：
- 使用二维列表
dp来存储子矩阵的最大和。 - 初始化
dp数组的第一行和第一列。 - 使用递推公式
- 使用二维列表
部署和测试
Java:
1. 保存代码:
- 将上面的 Java 代码保存为
MaxMatrixSum.java文件。
2. 编译代码:
- 您需要安装 Java 开发环境 (JDK) 并配置好
JAVA_HOME环境变量。 - 打开终端或命令行，并导航到保存 Java 代码的目录。
- 使用以下命令编译代码：
javac MaxMatrixSum.java
3. 运行代码:
- 使用以下命令运行编译后的 Java 类：
java MaxMatrixSum
4. 测试代码:
- 您可以在
main函数中修改输入矩阵来测试代码。 - 观察程序输出的最大矩阵和是否正确。
示例输出:
Maximum matrix sum: 15
JavaScript:
1. 保存代码:
- 将上面的 JavaScript 代码保存为
maxMatrixSum.js文件。
2. 运行代码:
- 您需要安装 Node.js 或使用支持 JavaScript 的 Web 浏览器。
- 打开终端或命令行，并导航到保存 JavaScript 代码的目录。
- 使用以下命令运行代码：
node maxMatrixSum.js
3. 测试代码:
- 您可以在代码中修改输入矩阵来测试代码。
- 观察程序输出的最大矩阵和是否正确。
示例输出:
Maximum matrix sum: 15
Python:
1. 保存代码:
- 将上面的 Python 代码保存为
max_matrix_sum.py文件。
2. 运行代码:
- 您需要安装 Python 解释器。
- 打开终端或命令行，并导航到保存 Python 代码的目录。
- 使用以下命令运行代码：
python max_matrix_sum.py
3. 测试代码:
- 您可以在代码中修改输入矩阵来测试代码。
- 观察程序输出的最大矩阵和是否正确。
示例输出:
Maximum matrix sum: 15
C:
1. 保存代码:
- 将上面的 C 代码保存为
maxMatrixSum.c文件。
2. 编译代码:
- 您需要安装 C 编译器和运行时环境。
- 具体步骤取决于您使用的编译器和操作系统。
- 一般来说，您可以使用以下命令进行编译：
gcc maxMatrixSum.c -o maxMatrixSum
3. 运行代码:
- 使用以下命令运行编译后的可执行文件：
./maxMatrixSum
4. 测试代码:
- 您可以在代码中修改输入矩阵来测试代码。
- 观察程序输出的最大矩阵和是否正确。
示例输出:
Maximum matrix sum: 15
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）