इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है। हमारा कार्य बढ़ते क्रम के अधिकतम उत्पाद को खोजना है।
समस्या का विवरण - हमें सरणी के तत्वों से किसी भी संभव आकार के बढ़ते क्रम के अधिकतम उत्पाद को खोजने की जरूरत है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
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. है