C++ প্রোগ্রামে n অ্যারে থেকে অর্ডার উপাদান বৃদ্ধির সর্বোচ্চ যোগফল

এই সমস্যায়, আমাদের nXm আকারের একটি 2-ডি ম্যাট্রিক্স দেওয়া হয়েছে। আমাদের কাজ হল n অ্যারে থেকে ক্রমবর্ধমান উপাদানগুলির সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।

প্রোগ্রামের বিবরণ − এখানে, আমাদের প্রতিটি সারি থেকে এমনভাবে একটি উপাদান নিয়ে উপাদানের সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে ith সারির উপাদানটি (i+1)তম সারির উপাদানের চেয়ে কম হয়। ইত্যাদি। যদি এমন কোন যোগফল সম্ভব না হয়, তাহলে −1 রিটার্ন করুন যাতে কোন ফলাফল সম্ভব না হয়।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

<প্রে>ম্যাট[][] ={ {4, 5, 1, 3, 6}, {5, 9, 2, 7, 12}, {13, 1, 3, 6, 8}, {10, 5 , 7, 2, 4}}

আউটপুট

ব্যাখ্যা

সর্বোচ্চ যোগফল তৈরি করতে ম্যাট্রিক্স থেকে উপাদান গ্রহণ করা:6 + 7 + 8 + 10 =31,6 অ্যারে 1 থেকে, সর্বোচ্চ মান। অ্যারে 2 থেকে 7, 12 (সর্বোচ্চ মান) বেছে নেওয়া একটি সমাধান প্রদান করতে পারে না। অ্যারে 3, 13 (সর্বোচ্চ মান) বেছে নেওয়া একটি সমাধান প্রদান করতে পারে না। 10 অ্যারে 4 থেকে, সর্বাধিক মান

সমাধান পদ্ধতি

সমস্যার সমাধান হল অ্যারের অ্যারের শেষ অ্যারে থেকে একটি উপাদান নির্বাচন করা এবং তারপরে প্রদত্ত উপাদানের চেয়ে ছোট সম্ভাব্য সবচেয়ে বড় উপাদান নির্বাচন করা।

এখন, এই সমাধানটি ব্যবহার করে, আমাদের কাছে একটি কেস আছে যখন itharray (সারিতে) কোন উপাদান নেই যা (i+1)তম অ্যারের (সারি) এলিমেন্টের চেয়ে কম। এখানে, আমরা −1 ফিরব।

অ্যারে সাজানো আমাদের সমাধানের দক্ষতার জন্য একটি ভাল সাহায্য হতে পারে। যেন ক্রমবর্ধমান ক্রম অনুসারে, বৃহত্তম উপাদানটি সূচক m−1-এ থাকবে এবং তারপরে ছোট হবে। অতএব, শর্ত পূরণকারী বৃহত্তম উপাদান খুঁজে পাওয়া সহজ।

অ্যালগরিদম

maxSum =0, currMax

শুরু করুন

ধাপ 1 −

অ্যারের অ্যারের প্রতিটি অ্যারে সাজান (প্রত্যেকটিতে ক্রমবর্ধমান ক্রমে উপাদান থাকবে)।

ধাপ 2 −

currMax =ম্যাট[n−1][m−1], শেষ উপাদান বা শেষ সারি। UpdatemaxSum, maxSum =currMax।

ধাপ 3 −

রোভাইজ ম্যাট্রিক্সের মধ্য দিয়ে লুপ করুন, i =n−2 থেকে 0।

ধাপ ৩.১ −

ম্যাটে সর্বাধিক উপাদান খুঁজুন [i][] যা ইনডেক্স j এ currMax থেকে ছোট।

পদক্ষেপ 3.2৷ −

যদি j <0, অর্থাৎ কোন মান পাওয়া যায় নি। ফেরত −1 .

পদক্ষেপ 3.3৷ −

 currMax আপডেট করুন। currMax =ম্যাট[i][j]।

ধাপ ৩.৪ −

আপডেট করুন maxSum, maxSum =currMax।

পদক্ষেপ 4৷ −

ম্যাক্সসম ফেরত দিন।

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

#include #define M 5 useing namespace std;int calcMaxSumMat(int mat[][M], int n) { for (int i =0; i =0; i−−) { for (j =M −1; j>=0; j−−) { if (mat[i][j]  আউটপুট
 n অ্যারে থেকে অর্ডার উপাদানের সর্বাধিক যোগফল হল 31