C++ 프로그램에서 위에서 아래로 행렬의 최대 합 경로

이 튜토리얼에서는 위에서 아래로 행렬에서 최대 합 경로를 찾는 프로그램에 대해 설명합니다.

이를 위해 N*N 크기의 행렬이 제공됩니다. 우리의 임무는 대각선으로 더 높은 셀로 이동하면서 위쪽 행에서 아래쪽 행까지의 최대 합 경로를 찾는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
//finding maximum sum path
int maxSum(int mat[SIZE][SIZE], int n) {
   if (n == 1)
      return mat[0][0];
   int dp[n][n];
   int maxSum = INT_MIN, max;
   for (int j = 0; j < n; j++)
      dp[n - 1][j] = mat[n - 1][j];
   for (int i = n - 2; i >= 0; i--) {
      for (int j = 0; j < n; j++) {
         max = INT_MIN;
         if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) max = dp[i + 1][j - 1];
            if (((j + 1) < n) && (max < dp[i + 1][j + 1])) max = dp[i + 1][j + 1];
               dp[i][j] = mat[i][j] + max;
      }
   }
   for (int j = 0; j < n; j++)
      if (maxSum < dp[0][j])
         maxSum = dp[0][j];
   return maxSum;
}
int main() {
   int mat[SIZE][SIZE] = {
      { 5, 6, 1, 7 },
      { -2, 10, 8, -1 },
      { 3, -7, -9, 11 },
      { 12, -4, 2, 6 }
    };
   int n = 4;
   cout << "Maximum Sum = " << maxSum(mat, n);
   return 0;
}

출력

Maximum Sum = 28