C++-এ n সংখ্যক অ্যারে থেকে ক্রমবর্ধমান এলিমেন্ট নিয়ে সর্বোচ্চ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

Nটি অ্যারে (প্রতিটির আকার M) দেওয়া থাকলে, প্রতিটি অ্যারে থেকে একটা করে এলিমেন্ট নিতে হবে যাতে আগের অ্যারের এলিমেন্ট ছোট হয় এবং মোট সম সর্বোচ্চ হয়।

সমাধানের পদ্ধতি (Gridi + Sorting)

1. প্রতিটি অ্যারে সর্ট করুন।
2. সর্বশেষ অ্যারে থেকে সবচেয়ে বড় এলিমেন্ট নিন।
3. পিছিয়ে আসতে আসতে প্রতিটি অ্যারে থেকে আগের নেওয়া এলিমেন্টের চেয়ে ছোট সবচেয়ে বড় এলিমেন্ট নিন।
4. যদি কোনো অ্যারেতে পাওয়া না যায়, 0 রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
#define M 4
using namespace std;

int maximumSum(int a[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(a[i], a[i] + M);
    
    int sum = a[n - 1][M - 1];
    int prev = a[n - 1][M - 1];
    
    for (int i = n - 2; i >= 0; i--) {
        for (int j = M - 1; j >= 0; j--) {
            if (a[i][j] < prev) {
                prev = a[i][j];
                sum += prev;
                break;
            }
        }
        if (j == -1) return 0; // j scope issue, fixed below
    }
    return sum;
}

// Fixed version:
int maximumSumFixed(int a[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(a[i], a[i] + M);
    
    int sum = a[n - 1][M - 1];
    int prev = a[n - 1][M - 1];
    bool found;
    
    for (int i = n - 2; i >= 0; i--) {
        found = false;
        for (int j = M - 1; j >= 0; j--) {
            if (a[i][j] < prev) {
                prev = a[i][j];
                sum += prev;
                found = true;
                break;
            }
        }
        if (!found) return 0;
    }
    return sum;
}

int main() {
    int arr[][M] = {
        {1, 7, 3, 4},
        {4, 2, 5, 1},
        {9, 5, 1, 8}
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maximumSumFixed(arr, n);
    return 0;
}

আউটপুট

18

ব্যাখ্যা

সর্টেড অ্যারে: [1,3,4,7] [1,2,4,5] [1,5,8,9]

পেছন থেকে: 9 → 5 (2nd array) → 4 (1st array) = 18

জটিলতা

• সময়: O(N × M log M)
• স্থান: O(1)