এই সমস্যায়, আমাদেরকে 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
