Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम में बाएं और दाएं अगले बड़े तत्व के सूचकांकों के उत्पाद का अधिकतम मान


इस समस्या में, हमें एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो बाएं और दाएं अगले बड़े तत्व के सूचकांकों के उत्पाद का अधिकतम मान निकाले।

समस्या विवरण

दी गई सरणी के लिए हमें left[i]*right[i] के अधिकतम मान का उत्पाद ढूंढना है। दोनों सरणियाँ इस प्रकार परिभाषित हैं -

left[i] = j, जैसे कि arr[i] < arr[j] और i > j। 
right[i] = j, जैसे कि arr[i] < arr[j] और i < j। 
*सरणी 1 अनुक्रमित है।

उदाहरण

इनपुट

arr[6] = {5, 2, 3, 1, 8, 6}

आउटपुट

15

व्याख्या

बाएं सरणी बनाना, left[] = {0, 1, 1, 3, 0, 5} 
right[] = {5, 3, 5, 5, 0, 0} 
सूचकांक उत्पाद: 
1 → 0*5 = 0 
2 → 1*3 = 3 
3 → 1*5 = 5 
4 → 3*5 = 15 
5 → 0*0 = 0 
6 → 0*5 = 0

अधिकतम उत्पाद

15

समाधान दृष्टिकोण

तत्व के बाएं और दाएं बड़े तत्व के सूचकांक के अधिकतम उत्पाद को ढूंढने के लिए। हम पहले बाएं और दाएं बड़े तत्व के सूचकांक ढूंढेंगे और तुलना के लिए उनका उत्पाद संग्रहीत करेंगे।

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

यदि स्टैक खाली है → वर्तमान सूचकांक पुश करें, tos = 1। Tos स्टैक का शीर्ष है। 
अन्यथा यदि arr[i] > arr[tos] → tos = 1।

इसका उपयोग करके हम सरणी के दिए गए तत्व के बाएं और दाएं सभी बड़े तत्वों के सूचकांक मान ढूंढ सकते हैं।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <bits/stdc++.h> 
using namespace std; 

int* findNextGreaterIndex(int a[], int n, char ch ) { 
    int* greaterIndex = new int [n]; 
    stack index; 
    
    if(ch == 'R'){ 
        for (int i = 0; i < n; ++i) { 
            while (!index.empty() && a[i] > a[index.top() - 1]) { 
                int indexVal = index.top(); 
                index.pop(); 
                greaterIndex[indexVal - 1] = i + 1; 
            } 
            index.push(i + 1); 
        } 
    } 
    else if(ch == 'L'){ 
        for (int i = n - 1; i >= 0; i--) { 
            while (!index.empty() && a[i] > a[index.top() - 1]) { 
                int indexVal = index.top(); 
                index.pop(); 
                greaterIndex[indexVal - 1] = i + 1; 
            } 
            index.push(i + 1); 
        } 
    } 
    return greaterIndex; 
} 

int calcMaxGreaterIndedxProd(int arr[], int n) { 
    int* left = findNextGreaterIndex(arr, n, 'L'); 
    int* right = findNextGreaterIndex(arr, n, 'R'); 
    int maxProd = -1000; 
    int prod; 
    
    for (int i = 1; i < n; i++) { 
        prod = left[i]*right[i]; 
        if(prod > maxProd) 
            maxProd = prod; 
    } 
    return maxProd; 
} 

int main() { 
    int arr[] = { 5, 2, 3, 1, 8, 6}; 
    int n = sizeof(arr) / sizeof(arr[1]); 
    cout<<"The maximum product of indexes of next greater on left and right is "<<calcMaxGreaterIndedxProd(arr, n); 
    return 0; 
}

आउटपुट

The maximum product of indexes of next greater on left and right is 15
  1. - C++ में 0 और 1 के सेगमेंट की अधिकतम लंबाई

    समस्या कथन एक स्ट्रिंग दी गई है जिसमें केवल 0 और 1 हैं। कार्य स्ट्रिंग के सेगमेंट की अधिकतम लंबाई ढूंढना है जैसे कि प्रत्येक सेगमेंट में 1 की संख्या 0 से अधिक हो। उदाहरण यदि इनपुट स्ट्रिंग 10111000001011 है तो उत्तर 12 होगा - पहला सेगमेंट लंबाई 7 का है 10111000001011 दूसरा सेगमेंट लंबाई 5 का है 10

  1. - C++ में N के चार गुणनखंड जिनका गुणनफल अधिकतम हो और योग N के बराबर हो

    मान लीजिए हमारे पास एक पूर्णांक N है। कार्य N के सभी गुणनखंड ढूंढना और N के चार गुणनखंडों का गुणनफल प्रदर्शित करना है, जैसे कि - उनके चार गुणनखंडों का योग N के बराबर हो चार गुणनखंडों का गुणनफल अधिकतम हो मान लीजिए संख्या 24 है, तो गुणनफल 1296 होगा। जैसा कि हम जानते हैं सभी गुणनखंड 1, 2, 3, 4, 6, 8,

  1. - C/C++ में लेफ्ट शिफ्ट और राइट शिफ्ट ऑपरेटर्स

    लेफ्ट शिफ्ट लेफ्ट शिफ्ट ऑपरेटर में, लेफ्ट ऑपरेंड का मान राइट ऑपरेंड द्वारा निर्दिष्ट बिट्स की संख्या से बाएं मूव होता है। उदाहरण #include <stdio.h> int main() { int y = 28; // 11100 int i = 0; for (i; i <= 3; ++i) printf(लेफ्ट शिफ्ट बाय %d: %d\n, i, y << i);