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

इस समस्या में, हमें 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