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

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


धनात्मक पूर्णांकों की सरणी दी गई है। ठीक 3 तत्वों वाले बढ़ते उपअनुक्रम का अधिकतम गुणनफल खोजें।

कुशल दृष्टिकोण: प्रत्येक तत्व के लिए बाएं तरफ सबसे बड़ा छोटा तत्व (सेट का उपयोग करके) और दाएं तरफ सबसे बड़ा तत्व ट्रैक करें।

उदाहरण: {10, 11, 9, 5, 6, 1, 20} → अधिकतम गुणनफल 2200 (10, 11, 20)।

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

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

long long int maxProduct(int arr[], int n) {
    int smaller[n];
    smaller[0] = -1;
    set S;
    for (int i = 0; i < n; i++) {
        auto j = S.insert(arr[i]);
        auto itc = j.first; --itc;
        if (itc != S.end()) smaller[i] = *itc;
        else smaller[i] = -1;
    }
    long long int result = INT_MIN;
    int max_right = arr[n - 1];
    for (int i = n - 2; i >= 1; i--) {
        if (arr[i] > max_right) max_right = arr[i];
        else if (smaller[i] != -1)
            result = max(1LL * smaller[i] * arr[i] * max_right, result);
    }
    return result;
}

int main() {
    int arr[] = {10, 11, 9, 5, 6, 1, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxProduct(arr, n) << endl;
    return 0;
}

आउटपुट

2200
  1. - C++ में आकार k के सबसीक्वेंस का अधिकतम गुणनफल

    इस समस्या में, हमें पूर्णांकों की एक सरणी arr[] और एक संख्या k दी गई है। हमारा कार्य C++ में आकार k के सबसीक्वेंस का अधिकतम गुणनफल ढूंढने के लिए एक प्रोग्राम बनाना है। समस्या विवरण - यहां, हमें आकार k का सबसीक्वेंस ढूंढना है, 1 <= k <= n जिसके तत्वों का गुणनफल अधिकतम हो। आइए एक उदाहरण से समस्

  1. - C++ में शब्द लंबाई का अधिकतम गुणनफल

    मान लीजिए हमारे पास words नामक एक स्ट्रिंग सरणी है, length(word[i]) * length(word[j]) का अधिकतम मान ढूंढें जहां दो शब्द सामान्य अक्षर साझा नहीं करेंगे। हम मान सकते हैं कि प्रत्येक शब्द में केवल लोअरकेस अक्षर होंगे। यदि ऐसी कोई दो शब्द मौजूद नहीं हैं, तो 0 लौटाएं।उदाहरण के लिए, यदि इनपुट [abcw, baz,

  1. - C++ में Number of Longest Increasing Subsequence

    मान लीजिए हमारे पास पूर्णांकों की एक अक्रमबद्ध सरणी है। हमें सबसे लंबी बढ़ती उपअनुक्रम (longest increasing subsequence) की संख्या ढूंढनी है, इसलिए यदि इनपुट [1, 3, 5, 4, 7] जैसा है, तो आउटपुट 2 होगा, क्योंकि बढ़ते उपअनुक्रम [1,3,5,7] और [1, 3, 4, 7] हैं।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे