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