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

C++ में बाएं और दाएं अगले बड़े तत्व के इंडेक्स गुणनफल का अधिकतम मान


सरणी दी गई है। प्रत्येक तत्व के लिए बाएं तरफ निकटतम बड़ा तत्व का इंडेक्स L(i) और दाएं तरफ निकटतम बड़ा तत्व का इंडेक्स R(i) खोजें। L(i) * R(i) का अधिकतम मान ज्ञात करें।

स्टैक का उपयोग करके दोनों तरफ के अगले बड़े तत्व O(n) में खोजें।

उदाहरण: {5, 4, 3, 4, 5} → अधिकतम गुणनफल 8।

C++ कार्यान्वयन

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

#define MAX 1000

vector nextGreaterInLeft(int a[], int n) {
    vector left_index(MAX, 0);
    stack s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top(); s.pop();
            left_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return left_index;
}

vector nextGreaterInRight(int a[], int n) {
    vector right_index(MAX, 0);
    stack s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top(); s.pop();
            right_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return right_index;
}

int LRProduct(int arr[], int n) {
    vector left = nextGreaterInLeft(arr, n);
    vector right = nextGreaterInRight(arr, n);
    int ans = -1;
    for (int i = 1; i <= n; i++) ans = max(ans, left[i] * right[i]);
    return ans;
}

int main() {
    int arr[] = {5, 4, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << LRProduct(arr, n);
    return 0;
}

आउटपुट

8
  1. C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल

    इस समस्या में, हमें n नोड्स के साथ एक अविभाजित कनेक्टेड ट्री T दिया गया है। हमारा कार्य C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए एक प्रोग्राम बनाना है। समस्या विवरण - ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए। हम सभी गैर-प्रतिच्छेदी पथ ढूंढेंगे औ

  1. - C++ में अधिकतम उत्पाद वाले चौगुनी (Quadruples) की संख्या ज्ञात करें

    मान लीजिए हमारे पास n तत्वों का एक पूर्णांक सरणी है। हमें सरणी में एक चौगुनी का अधिकतम उत्पाद ढूंढना है। इसलिए यदि सरणी [3, 5, 20, 6, 10] की तरह है, तो अंतिम उत्पाद 6000 है, और चौगुनी में तत्व 10, 5, 6, 20 हैं। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे: सरणी को आरोही क्रम में सॉर्ट करें मान ली

  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);