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

C++ प्रोग्राम में बाएँ और दाएँ पर अगले बड़े के अनुक्रमणिका का अधिकतम उत्पाद

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

समस्या का विवरण -

दिए गए सरणी के लिए हमें बाएँ [i] * दाएँ [i] के अधिकतम मान का गुणनफल खोजना होगा। दोनों सरणियों को -

. के रूप में परिभाषित किया गया है
left[i] = j, such that arr[i] <’. ‘ arr[j] and i > j.
right[i] = j, such that arr[i] < arr[j] and i < j.
*The array is 1 indexed.

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

आउटपुट

15

स्पष्टीकरण

Creating left array,
left[] = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}
Index products :
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

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

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

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

If stack is empty −> push current index, tos = 1. Tos is top of the stack
Else if 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<int> 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 के सेगमेंट की अधिकतम लंबाई

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

  1. अधिकतम उत्पाद के साथ एन के चार कारक खोजें और सी ++ में एन के बराबर योग करें

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

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

    बाएं शिफ़्ट लेफ्ट शिफ्ट ऑपरेटर में, लेफ्ट ऑपरेंड वैल्यू को राइट ऑपरेंड द्वारा निर्दिष्ट बिट्स की संख्या से बायीं ओर ले जाया जाता है। यहाँ C भाषा में लेफ्ट शिफ्ट ऑपरेटर का उदाहरण दिया गया है, उदाहरण #include <stdio.h> int main() {    int y = 28; // 11100    int i = 0; &n