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