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

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


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

DP दृष्टिकोण: mpis[i] = इंडेक्स i पर समाप्त होने वाले बढ़ते उपअनुक्रम का अधिकतम गुणनफल।

उदाहरण: {3, 100, 4, 5, 150, 6} → अधिकतम गुणनफल 45000 (3, 100, 150)।

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

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll lis(ll arr[], ll n) {
    ll mpis[n];
    for (int i = 0; i < n; i++) mpis[i] = arr[i];
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && mpis[i] < mpis[j] * arr[i])
                mpis[i] = mpis[j] * arr[i];
    return *max_element(mpis, mpis + n);
}

int main() {
    ll arr[] = {3, 100, 4, 5, 150, 6};
    ll n = sizeof(arr) / sizeof(arr[0]);
    printf("%lld", lis(arr, n));
    return 0;
}

आउटपुट

45000
  1. - C++ में तीन संख्याओं का अधिकतम गुणनफल

    मान लीजिए हमारे पास एक पूर्णांक सरणी है; हमें तीन संख्याएं ढूंढनी हैं जिनका गुणनफल अधिकतम हो फिर अधिकतम गुणनफल वापस करना है। इसलिए, यदि इनपुट [1,1,2,3,3] जैसा है, तो आउटपुट 18 होगा, क्योंकि तीन तत्व हैं [2,3,3]। इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे: सरणी nums को सॉर्ट करें l := 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] हैं।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे