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

C++ में Number of Longest Increasing Subsequence


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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • n := num सरणी का आकार, len और cnt नामक दो सरणियाँ आकार n की बनाएं, और उन्हें मान 1 से भरें।
  • lis := 1
  • i को 1 से n तक की रेंज में
    • j को 0 से i - 1 तक की रेंज में
      • यदि nums[i] > nums[j], तो
        • यदि len[j] + 1 > len[i], तो len[i] := len[j] + 1, और cnt[i] := cnt[j]
        • अन्यथा जब len[j] + 1 = len[j], तो cnt[i] := cnt[i] + cnt[j]
      • lis := lis और len[j] का अधिकतम
  • ans := 0
  • i को 0 से n - 1 तक की रेंज में
    • यदि len[i] = lis, तो ans := ans + cnt[j]
  • ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h> using namespace std; class Solution { public:    int findNumberOfLIS(vector<int>& nums) {       int n = nums.size();       vector <int> len(n, 1), cnt(n, 1);       int lis = 1;       for(int i = 1; i < n; i++){          for(int j = 0; j < i; j++){             if(nums[i] > nums[j]){                if(len[j] + 1 > len[i]){                   len[i] = len[j] + 1;                   cnt[i] = cnt[j];                }                else if(len[j] + 1 == len[i]){                   cnt[i] += cnt[j];                }             }             lis = max(lis, len[i]);          }       }       int ans = 0;       for(int i = 0; i < n; i++){          if(len[i] == lis)ans += cnt[i];       }       return ans;    } }; main(){    Solution ob;    vector<int> v = {1,3,5,4,7};    cout << (ob.findNumberOfLIS(v)); }

इनपुट

[1,3,5,4,7]

आउटपुट

2

  1. - C++ प्रोग्राम: लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS)

    एक सबसीक्वेंस तत्वों के समूह का वही क्रम वाला अनुक्रम है। अनुक्रम stuv के लिए, सबसीक्वेंस हैं stu, tuv, suv, आदि। लंबाई n के एक स्ट्रिंग के लिए, उस स्ट्रिंग से सबसीक्वेंस बनाने के 2^n तरीके हो सकते हैं। उदाहरण स्ट्रिंग्स ABCDGH और AEDFHR के लिए सबसे लंबी सामान्य सबसीक्वेंस की लंबाई 3 है। #include &l

  1. - C++ प्रोग्राम: दी गई सीक्वेंस का लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस ढूंढना

    लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस (LIS) एक ऐसा सबसीक्वेंस होता है जहां प्रत्येक एलिमेंट अपने पिछले एलिमेंट से बड़ा होता है। यहां हम पूर्णांकों के एक सेट से लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस की लंबाई ढूंढने का प्रयास करेंगे। इनपुट: पूर्णांकों का सेट {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 1

  1. - C++ में CHAR_BIT

    CHAR_BIT क्या है? CHAR_BIT एक बाइट में बिट्स की संख्या दर्शाता है। <climits> या <limits.h> हेडर में परिभाषित। आमतौर पर 8 बिट्स प्रति बाइट होता है। C++ प्रोग्राम उदाहरण #include <bits/stdc++.h> using namespace std; int main() { int x = 28; int total_bits = CHAR_BIT * size