सी ++ प्रोग्राम में ऊपर से नीचे तक मैट्रिक्स में अधिकतम योग पथ

इस ट्यूटोरियल में, हम ऊपर से नीचे तक मैट्रिक्स में अधिकतम योग पथ खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।

इसके लिए हमें 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