অ্যারেতে ট্রিপলেট (আকার ৩ এর সাবসিকোয়েন্স) এর সর্বোচ্চ গুণফল (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n সংখ্যক পূর্ণসংখ্যা সমন্বিত একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল অ্যারেতে ট্রিপলেট (আকার ৩ এর সাবসিকোয়েন্স) এর সর্বোচ্চ গুণফল বের করা। এখানে, আমরা সর্বোচ্চ গুণফল দেয় এমন ট্রিপলেট খুঁজে বের করব এবং গুণফল ফেরত দিব।

arr[] = {9, 5, 2, 11, 7, 4}

693

এখানে, আমরা অ্যারেতে সব উপাদান থেকে সর্বোচ্চ গুণফল দেয় এমন ট্রিপলেট খুঁজে বের করব। maxProd = 9 * 11 * 7 = 693

এই সমস্যার একাধিক সমাধান হতে পারে। আমরা এখানে সেগুলো আলোচনা করব।

এই পদ্ধতিতে, আমরা সরাসরি অ্যারে লুপ চালিয়ে সব সম্ভাব্য ট্রিপলেট বের করব। প্রতিটি ট্রিপলেটের উপাদানগুলোর গুণফল বের করে সবচেয়ে বড় গুণফল ফেরত দিব।

আরম্ভিকরণ:

maxProd = -1000

ধাপ ১: তিনটি নেস্টেড লুপ তৈরি করুন: Loop 1: i → 0 থেকে n-3 Loop 2: j → i থেকে n-2 Loop 3: k → j থেকে n-1

ধাপ ১.১: গুণফল বের করুন, prod = arr[i]*arr[j]*arr[k]。

ধাপ ১.২: if prod > maxProd → maxProd = prod।

ধাপ ৩: maxProd ফেরত দিন।

#include 
using namespace std;

int calcMaxProd(int arr[], int n) {
    int maxProd = -1000;
    int prod;
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            for (int k = j + 1; k < n; k++) {
                prod = arr[i] * arr[j] * arr[k];
                if (maxProd < prod)
                    maxProd = prod;
            }
    return maxProd;
}

int main() {
    int arr[] = { 9, 5, 2, 11, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum product of a triplet in array is " << calcMaxProd(arr, n);
    return 0;
}

Maximum product of a triplet in array is 693

এই পদ্ধতিতে, আমরা অ্যারেটি নিম্নক্রমে সর্ট করব। সর্ট করা অ্যারেতে সর্বোচ্চ গুণফল ট্রিপলেট থাকবে:

(arr[0], arr[1], arr[2])
(arr[0], arr[n-1], arr[n-2])

আমরা এই দুটি ট্রিপলেটের গুণফলের মধ্যে সর্বোচ্চটি ফেরত দিব।

ধাপ ১: দেওয়া অ্যারেটি নিম্নক্রমে সর্ট করুন।

ধাপ ২: ট্রিপলেটের গুণফল বের করুন: maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n-1]*arr[n-2]

ধাপ ৩: if(maxTriplet1 > maxTriplet2) → return maxTriplet1

ধাপ ৪: else → return maxTriplet2।

#include 
using namespace std;

int calcMaxProd(int arr[], int n) {
    sort(arr, arr + n, greater<>());
    int maxTriplet1 = arr[0] * arr[1] * arr[2];
    int maxTriplet2 = arr[0] * arr[n - 1] * arr[n - 2];
    if (maxTriplet1 > maxTriplet2)
        return maxTriplet1;
    return maxTriplet2;
}

int main() {
    int arr[] = { 9, 5, 2, 11, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum product of a triplet in array is " << calcMaxProd(arr, n);
    return 0;
}

Maximum product of a triplet in array is 693

যেহেতু আমরা জানি সর্বোচ্চ গুণফল ট্রিপলেট নিচের দুটির যেকোনো একটিতে হতে পারে:

(maximum, second_max, third_max)
(maximum, minimum, second_min)

তাই আমরা সরাসরি অ্যারে ট্রভার্স করে এই মানগুলো বের করতে পারি এবং সেগুলো ব্যবহার করে সর্বোচ্চ গুণফল ট্রিপলেট বের করতে পারি।

আরম্ভিকরণ:

max = -1000, secMax = -1000, thirdMax = -1000
min = 10000, secMin = 10000

ধাপ ১: অ্যারে লুপ করুন i → 0 থেকে n-1।

ধাপ ১.১: if(arr[i] > max) → thirdMax = secMax, secMax = max, max = arr[i]

ধাপ ১.২: else if(arr[i] > secMax) → thirdMax = secMax, secMax = arr[i]

ধাপ ১.৩: else if(arr[i] > thirdMax) → thirdMax = arr[i]

ধাপ ১.৪: if(arr[i] < min) → secMin = min, min = arr[i]

ধাপ ১.৫: else if(arr[i] < secMin) → secMin = arr[i]

ধাপ ২: triplet1 = max * secMax * thirdMax, triplet2 = max * min * secMin

ধাপ ৩: if(triplet1 > triplet2) → return triplet1

ধাপ ৪: else → return triplet2

#include 
using namespace std;

int calcMaxProd(int arr[], int n) {
    int max = -1000, secMax = -1000, thirdMax = -1000;
    int min = 1000, secMin = 1000;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] > max) {
            thirdMax = secMax;
            secMax = max;
            max = arr[i];
        } else if (arr[i] > secMax) {
            thirdMax = secMax;
            secMax = arr[i];
        } else if (arr[i] > thirdMax)
            thirdMax = arr[i];
        
        if (arr[i] < min) {
            secMin = min;
            min = arr[i];
        } else if (arr[i] < secMin)
            secMin = arr[i];
    }
    
    int triplet1 = max * secMax * thirdMax;
    int triplet2 = max * secMin * min;
    if (triplet1 > triplet2)
        return triplet1;
    return triplet2;
}

int main() {
    int arr[] = { 9, 5, 2, 11, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum product of a triplet in array is " << calcMaxProd(arr, n);
    return 0;
}

Maximum product of a triplet in array is 693