数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++矩阵最大路径和
在这个问题中，我们给定一个大小为M*N的二维矩阵。我们的任务是创建一个程序来查找矩阵中的最大路径和。
这里，矩阵中的最大路径和定义为从第一行到最后一行所有元素的总和。允许的遍历路径移动是向下移动和对角移动。起点和终点可以分别是矩阵的第一行和最后行的任何元素。
让我们来看一个例子来理解这个问题
输入 −
matrix [][] = 3 5 9 1 7 2 4 8 6
输出 − 24
解释 − 最大路径将是 9 → 7 → 8。
为了解决这个问题，我们将从数组顶部开始，找到第一行中最大的元素，并将其存储到maxSum中。然后遍历矩阵并查找路径中出现的最大值。如果新值更大，则更新maxSum，否则不更新。一旦遍历完整个矩阵并创建了路径，就返回maxSum。
示例
查找矩阵中最大路径和的程序 −
#include <iostream>
#define N 3
#define M 3
using namespace std;
int maxPathSum(int mat[][M]){
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++) {
if (j > 0 && j < M - 1)
mat[i][j] += max(mat[i - 1][j], max(mat[i - 1][j - 1],mat[i - 1][j + 1]));
else if (j > 0)
mat[i][j] += max(mat[i - 1][j],
mat[i - 1][j - 1]);
else if (j < M - 1)
mat[i][j] += max(mat[i - 1][j],
mat[i - 1][j + 1]);
}
}
int maxSum = mat[N-1][0];
for (int j = 1; j < M; j++)
maxSum = max(mat[N-1][j], maxSum);
return maxSum;
}
int main(){
int matrix[N][M] = {
{3, 5, 9 },
{1, 7, 2},
{4, 8, 6}};
cout<<"The maximum path sum of matrix is : "<<maxPathSum(matrix);
return 0;
}输出
The maximum path sum of matrix is : 24
更新于: 2020年6月3日
685 次浏览
广告