C++ प्रोग्राम में आकार 3 के बढ़ते उपअनुक्रम का अधिकतम उत्पाद

इस समस्या में, हमें n धनात्मक पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो आकार 3 के बढ़ते उपअनुक्रम का अधिकतम उत्पाद ढूंढे।

समस्या विवरण

यहां, हमें सरणी के 3 तत्वों का अधिकतम उत्पाद ढूंढना है जैसे कि वे एक बढ़ता उपअनुक्रम बनाएं और सरणी सूचकांक भी बढ़ते हों यानी

arr[i]*arr[j]*arr[k] अधिकतम हो, arr[i]

उदाहरण
इनपुट
arr = {5, 9, 2, 11, 4, 7}

आउटपुट
495

व्याख्या
दिए गए शर्त को पूरा करने वाले आकार 3 के सभी उपसरणी हैं:
(5, 9, 11), उत्पाद = 5*9*11 = 495
(2, 4, 7), उत्पाद = 2*4*7 = 56
अधिकतम = 495

समाधान दृष्टिकोण
समस्या को हल करने का एक सरल दृष्टिकोण सरणी को लूप करना और दी गई शर्त को पूरा करने वाले आकार 3 के सभी उपसरणी ढूंढना है। तत्वों का उत्पाद ढूंढें और सभी उत्पादों में से अधिकतम वापस करें।

एल्गोरिदम
आरंभीकरण -
maxProd = -1000

चरण 1 -
लूप i → 0 से n-3 तक

चरण 1.1 -
लूप j → i से n-2 तक

चरण 1.1.1 -
if(arr[i]< arr[j]) → लूप k → j से n-1 तक

चरण 1.1.1.1 -
if(arr[j] < arr[k]) → prod = arr[i]*arr[j]*arr[k] ढूंढें।

चरण 1.1.1.2 -
if(maxProd > prod) → maxProd = prod।

चरण 2 -
maxProd वापस करें।

उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <iostream> 
using namespace std; 

int calcMaxProd(int arr[], int n){ 
    int maxProd = -1000; 
    int prod; 
    for (int i = 0; i < n - 2; i++) 
        for (int j = i + 1; j < n - 1; j++) 
            if(arr[i] < arr[j]){ 
                for (int k = j + 1; k < n; k++){ 
                    if(arr[j] < arr[k]){ 
                        prod = arr[i] * arr[j] * arr[k]; 
                        if(maxProd < prod) 
                            maxProd = prod; 
                    } 
                } 
            } 
    return maxProd; 
} 

int main(){ 
    int arr[] = { 5, 9, 2, 11, 4, 7 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout<<"The maximum product of an increasing subsequence of size 3 is "<<calcMaxProd(arr, n); 
    return 0; 
}

आउटपुट
The maximum product of an increasing subsequence of size 3 is 495

यह समाधान आसान है लेकिन 3 नेस्टेड लूप का उपयोग करता है जिससे समय जटिलता O(n³) क्रम की हो जाती है। तो, आइए समस्या का एक कुशल समाधान देखें,

इस समाधान में, हम सरणी के तत्वों को सूचकांक 1 से n-2 तक लेंगे। और इसे हमारे 3 तत्व उपसरणी का मध्य तत्व मानेंगे। और फिर बाकी दो तत्वों को सरणी से ढूंढेंगे।
सूचकांक i से कम वाले सरणी में arr[i] से छोटा तत्व। 
सूचकांक i से अधिक वाले सरणी में arr[i] से बड़ा तत्व।

सबसे छोटा तत्व सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग करके ढूंढा जाता है और सबसे बड़े के लिए, हम दाएं से बाएं पार करेंगे और दाएं में अधिकतम तत्व ढूंढेंगे।

दोनों मान मिलने के बाद, हम तत्व उपसरणी का उत्पाद ढूंढेंगे और फिर सभी की तुलना करके maxProd ढूंढेंगे।

उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include<bits/stdc++.h> 
using namespace std; 

long calMaxSubSeqProd(int arr[] , int n) { 
    int smallerLeftEle[n]; 
    smallerLeftEle[0] = -1 ; 
    set small ; 
    for (int i = 0; i < n ; i++) { 
        auto it = small.insert(arr[i]); 
        auto val = it.first; 
        --val; 
        if (val != small.end()) 
            smallerLeftEle[i] = *val; 
        else 
            smallerLeftEle[i] = -1; 
    } 
    long maxProd = -10000; 
    long prod ; 
    int greaterRightEle = arr[n-1]; 
    for (int i= n-2 ; i >= 1; i--) { 
        if (arr[i] > greaterRightEle) 
            greaterRightEle = arr[i]; 
        else if (smallerLeftEle[i] != -1){ 
            prod = smallerLeftEle[i]*arr[i]*greaterRightEle; 
            if(prod > maxProd) 
                maxProd = prod; 
        } 
    } 
    return maxProd; 
} 

int main() { 
    int arr[] = {5, 9, 2, 11, 4, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout<<"The maximum product of an increasing subsequence of size 3 is "<<calMaxSubSeqProd(arr, n); 
    return 0; 
}

आउटपुट
The maximum product of an increasing subsequence of size 3 is 495