n সংখ্যক অ্যারে থেকে ক্রমবর্ধমান কালে উপাদান নেয়ার সর্বোচ্চ যোগফল (C++ প্রোগ্রাম)

এখানে, আমাদের প্রতিটি সারি থেকে একটি করে উপাদান নিয়ে সর্বোচ্চ যোগফল বের করতে হবে যেন i-তম সারির উপাদান (i+1)-তম সারির উপাদানের চেয়ে ছোট হয়। এবং এভাবে চলতে থাকবে। যদি এমন কোনো যোগফল সম্ভব না হয়, তবে -1 ফেরত দিতে হবে যা কোনো ফলাফল সম্ভব নয় বলে বোঝাবে।

mat[][] = { {4, 5, 1, 3, 6}, {5, 9, 2, 7, 12}, {13, 1, 3, 6, 8}, {10, 5, 7, 2, 4} }

31

ম্যাট্রিক্স থেকে উপাদান নিয়ে সর্বোচ্চ যোগফল তৈরি: 6 + 7 + 8 + 10 = 31
6: ১ম অ্যারেতে সর্বোচ্চ মান।
7: ২য় অ্যারেতে, 12 (সর্বোচ্চ মান) নিলে সমাধান সম্ভব নয়।
8: ৩য় অ্যারেতে, 13 (সর্বোচ্চ মান) নিলে সমাধান সম্ভব নয়।
10: ৪র্থ অ্যারেতে সর্বোচ্চ মান।

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

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

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

আরম্ভিকরণ: maxSum = 0, currMax

ধাপ ১: অ্যারে সমূহের প্রতিটি অ্যারে (সারি) সর্ট করুন (প্রতিটিতে উপাদানগুলো ক্রমবর্ধমান কালে থাকবে)।

ধাপ ২: currMax = mat[n-1][m-1], অর্থাৎ শেষ সারির শেষ উপাদান। maxSum আপডেট করুন, maxSum = currMax।

ধাপ ৩: ম্যাট্রিক্সের সারি অনুযায়ী লুপ চালান, i = n-2 থেকে 0।

ধাপ ৩.১: mat[i][]-এ currMax-এর চেয়ে ছোট সর্বোচ্চ উপাদান j ইনডেক্সে খুঁজুন।

ধাপ ৩.২: যদি j < 0 হয়, অর্থাৎ কোনো মান পাওয়া যায়নি। ফেরত দিন -1।

ধাপ ৩.৩: currMax আপডেট করুন। currMax = mat[i][j]。

ধাপ ৩.৪: maxSum আপডেট করুন, maxSum += currMax।

ধাপ ৪: maxSum ফেরত দিন।

#include 
#define M 5
using namespace std;

int calcMaxSumMat(int mat[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(mat[i], mat[i] + M);
    
    int maxSum = mat[n - 1][M - 1];
    int currMax = mat[n - 1][M - 1];
    int j;
    
    for (int i = n - 2; i >= 0; i--) {
        for (j = M - 1; j >= 0; j--) {
            if (mat[i][j] < currMax) {
                currMax = mat[i][j];
                maxSum += currMax;
                break;
            }
        }
        if (j == -1)
            return 0;
    }
    return maxSum;
}

int main() {
    int mat[][M] = {
        {4, 5, 1, 3, 6},
        {5, 9, 2, 7, 12},
        {12, 1, 3, 6, 8},
        {10, 5, 7, 2, 4}
    };
    int n = sizeof(mat) / sizeof(mat[0]);
    cout << "The maximum sum of increasing order elements from n arrays is " << calcMaxSumMat(mat, n);
    return 0;
}

The maximum sum of increasing order elements from n arrays is 31