इस समस्या में, हमें आकार n की एक सरणी arr[] दी गई है। हमारा कार्य बढ़ते उपअनुक्रम का अधिकतम उत्पाद ढूंढना है।
समस्या विवरण
हमें सरणी के तत्वों से किसी भी आकार के बढ़ते उपअनुक्रम का अधिकतम उत्पाद ढूंढना है।
उदाहरण
इनपुट
arr[] = {5, 4, 6, 8, 7, 9}
आउटपुट
2160
व्याख्या
सभी बढ़ते उपअनुक्रम:
{5,6,8,9}. उत्पाद = 2160
{5,6,7,9}. उत्पाद = 1890
यहां, हमने केवल अधिकतम आकार के उपअनुक्रम पर विचार किया है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करना है। इसके लिए, हम सरणी के दिए गए तत्व तक अधिकतम उत्पाद बढ़ते उपअनुक्रम को संग्रहीत करेंगे और फिर एक सरणी में संग्रहीत करेंगे।
एल्गोरिदम
आरंभीकरण -
prod[] को arr[] के तत्वों से। maxProd = -1000
चरण 1 -
लूप i → 0 से n-1 तक
चरण 1.1 -
लूप i → 0 से i तक
चरण 1.1.1
जांचें कि क्या वर्तमान तत्व बढ़ता उपअनुक्रम बनाता है यानी arr[i]>arr[j] और arr[i]*prod[j]> prod[i] → prod[i] = prod[j]*arr[i]
चरण 2 -
सरणी का अधिकतम तत्व ढूंढें। चरण 3 और 4 का पालन करें।
चरण 3 -
लूप i → 0 से n-1 तक
चरण 4 -
if(prod[i] > maxProd) → maxPord = prod[i]
चरण 5 -
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
