এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল ক্রমবর্ধমান অনুসৃতির সর্বোচ্চ পণ্য খুঁজে বের করা।
সমস্যা বর্ণনা − আমাদের অ্যারের উপাদানগুলি থেকে সম্ভাব্য যেকোনো আকারের পরবর্তী ক্রমবর্ধমান সর্বোচ্চ গুণফল খুঁজে বের করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {5, 4, 6, 8, 7, 9} আউটপুট
2160
ব্যাখ্যা
All Increasing subsequence:
{5,6,8,9}. Prod = 2160
{5,6,7,9}. Prod = 1890
Here, we have considered only max size subsequence. সমাধান পদ্ধতি
ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করে সমস্যার একটি সহজ সমাধান। এর জন্য, আমরা অ্যারের প্রদত্ত এলিমেন্ট পর্যন্ত সর্বাধিক পণ্য বাড়তে থাকা পরবর্তীতে সংরক্ষণ করব এবং তারপর একটি অ্যারেতে সংরক্ষণ করব।
অ্যালগরিদম
শুরু করুন −
prod[] with elements of arr[]. maxProd = −1000
ধাপ 1 −
Loop for i −> 0 to n−1
পদক্ষেপ 1.1৷ −
Loop for i −> 0 to iলুপ করুন
ধাপ 1.1.1৷
Check if the current element creates an increasing subsequence i.e. arr[i]>arr[j] and arr[i]*prod[j]> prod[i] −> prod[i] = prod[j]*arr[i]
ধাপ 2 −
find the maximum element of the array. Following steps 3 and 4.
ধাপ 3 −
Loop form i −> 0 to n−1
পদক্ষেপ 4৷ −
if(prod[i] > maxProd) −> maxPord = prod[i]
ধাপ 5 −
return maxProd.
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
#include <iostream>
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
