বাড়মান সাবসিকোয়েন্সের সর্বোচ্চ গুণফল (C++ প্রোগ্রাম)

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

অ্যারেতে উপাদান থেকে যেকোনো আকারের বাড়মান সাবসিকোয়েন্সের সর্বোচ্চ গুণফল বের করতে হবে।

arr[] = {5, 4, 6, 8, 7, 9}

2160

সকল বাড়মান সাবসিকোয়েন্স:
{5,6,8,9}. গুণফল = 2160
{5,6,7,9}. গুণফল = 1890
এখানে, আমরা শুধু সর্বোচ্চ আকারের সাবসিকোয়েন্স বিবেচনা করেছি।

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

আরম্ভিকরণ:

prod[] অ্যারেতে উপাদান arr[]-এর সাথে। maxProd = -1000

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

ধাপ ১.১: j → 0 থেকে i পর্যন্ত লুপ।

ধাপ ১.১.১: চেক করুন বর্তমান উপাদান বাড়মান সাবসিকোয়েন্স তৈরি করে কিনা অর্থাৎ arr[i] > arr[j] এবং arr[i]*prod[j] > prod[i] → prod[i] = prod[j]*arr[i]

ধাপ ২: অ্যারেতে সর্বোচ্চ উপাদান বের করুন। ধাপ ৩ এবং ৪ অনুসরণ করুন।

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

ধাপ ৪: if(prod[i] > maxProd) → maxProd = prod[i]

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

#include 
using namespace std;

long calcMaxProdSubSeq(long arr[], int n) {
    long maxProdSubSeq[n];
    for (int i = 0; i < n; i++)
        maxProdSubSeq[i] = arr[i];
    
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && maxProdSubSeq[i] < (maxProdSubSeq[j] * arr[i]))
                maxProdSubSeq[i] = maxProdSubSeq[j] * arr[i];
    
    long maxProd = -1000;
    for (int i = 0; i < n; i++) {
        if (maxProd < maxProdSubSeq[i])
            maxProd = maxProdSubSeq[i];
    }
    return maxProd;
}

int main() {
    long arr[] = {5, 4, 6, 8, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum product of an increasing subsequence is " << calcMaxProdSubSeq(arr, n);
    return 0;
}

The maximum product of an increasing subsequence is 2160