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