অ্যারেতে সর্বোচ্চ গুণফল উপাদান সমূহ (C++ প্রোগ্রাম)

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

এখানে, আমাদের অ্যারেতে উপাদান সমূহের সর্বোচ্চ সম্ভাব্য গুণফল হিসাব করতে হবে।

উপাদান সমূহ (Subset): একটি অ্যারে sub[] হল অ্যারে arr[]-এর উপাদান সমূহ যদি sub[]-এর সব উপাদান arr[]-এ থাকে।

arr[] = {4, 5, 2, -1, 3}

40

উপাদান সমূহ sub[] = {4, 5, 2}
গুণফল = 4*5*2 = 40

একটি সহজ পদ্ধতি হল অ্যারেতে সব সম্ভাব্য উপাদান সমূহ তৈরি করা। তাদের গুণফল বের করা এবং সর্বোচ্চটি ফেরত দেওয়া। এই সমাধান বাস্তবায়ন করা সহজ হলেও নেস্টেড লুপের কারণে এর কমপ্লেক্সিটি O(n²*n) হয়।

দক্ষ সমাধান: অ্যারেতে নেগেটিভ (nofNeg) এবং শূন্য (nof0) এর সংখ্যা গণনা করে তারপর এই শর্তগুলো অনুযায়ী maxProd হিসাব করা।

ক্ষেত্র ১ (nof0 = 0 এবং nofNeg জোড়) - অ্যারেতে সকল উপাদান গুণফলে বিবেচনা করুন।
maxProd = arr[0] * arr[1] * … arr[n-1]

ক্ষেত্র ২ (nof0 = 0 এবং nofNeg বিজোড়) - অ্যারেতে সকল উপাদান বিবেচনা করুন বাদ দিয়ে অ্যারেতে সবচেয়ে বড় নেগেটিভ উপাদান (০-এর সবচেয়ে কাছাকাছি)।

ক্ষেত্র ৩ (nof0 != 0) - গুণফলে অ্যারেতে সকল শূন্য বাদ দিন। এবং ক্ষেত্র ১ এবং ২ এর মতো করুন।

বিশেষ ক্ষেত্র: শুধু একটি উপাদান ০ ছাড়া নেগেটিভ। maxProd = 0।

আরম্ভিকরণ:

maxProd = 1;

ধাপ ১: অ্যারে লুপ চালিয়ে nof0 (শূন্যের সংখ্যা) এবং nofNeg (নেগেটিভের সংখ্যা) গণনা করুন, এবং maxProd বের করুন। maxProd = maxProd*arr[i], i → 0 থেকে n-1।

ধাপ ২: নিচের ক্ষেত্রগুলো বিবেচনা করুন -

ক্ষেত্র ১ - if(nofNeg%2 == 0): maxProd
ক্ষেত্র ২ - if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg)
ক্ষেত্র ৩ - if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.

maxProd প্রিন্ট করুন।

#include 
using namespace std;

int findMaxSubsetProd(int arr[], int n) {
    int larNeg = -1000;
    int nofNeg = 0, Nof0 = 0;
    int maxProd = 1;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            Nof0++;
            continue;
        } else if (arr[i] < 0) {
            nofNeg++;
            if (larNeg < arr[i])
                larNeg = arr[i];
        }
        maxProd = maxProd * arr[i];
    }
    
    if (nofNeg % 2 == 0) {
        return maxProd;
    } else if (nofNeg % 2 != 0)
        return (maxProd / larNeg);
    
    if (Nof0 == (n - 1) && nofNeg == 1)
        return 0;
    
    return maxProd;
}

int main() {
    int arr[] = {4, -2, 5, -1, 3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum product subset of an array is " << findMaxSubsetProd(arr, n);
    return 0;
}

The maximum product subset of an array is 720