C++에서 행렬의 최대 경로 합계

이 문제에서는 크기가 M*N인 2D 행렬이 제공됩니다. 우리의 임무는 행렬에서 최대 경로 합을 찾는 프로그램을 만드는 것입니다.

여기서 행렬의 최대 경로 합은 마지막 행까지 한 행에 대한 모든 요소의 합으로 정의됩니다. 경로 횡단에 허용되는 이동은 아래쪽 이동과 대각선 이동입니다. 시작과 끝은 각각 행렬의 첫 번째 행과 마지막 행의 모든 ​​요소가 될 수 있습니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 -

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