Đường dẫn tổng tối đa trong ma trận từ trên xuống dưới trong Chương trình C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm đường dẫn tổng lớn nhất trong một ma trận từ trên xuống dưới.

Đối với điều này, chúng tôi sẽ được cung cấp một ma trận có kích thước N * N. Nhiệm vụ của chúng ta là tìm đường tổng lớn nhất từ ​​hàng trên xuống hàng dưới trong khi di chuyển đến ô cao hơn theo đường chéo.

Ví dụ

#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;
}

Đầu ra

Maximum Sum = 28