C++でのマトリックスの最大パス合計

この問題では、サイズM*Nの2D行列が与えられます。私たちのタスクは、マトリックス内の最大パス合計を見つけるプログラムを作成することです。

ここで、行列の最大パス合計は、1行から最後の行までのすべての要素の合計として定義されます。パスを横断するために許可されている移動は、下向きの移動と斜めの移動です。開始点と終了点は、それぞれマトリックスの最初の行と最後の行の任意の要素にすることができます。

問題を理解するために例を見てみましょう

入力 −

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