C++ में सबसे लंबे समय तक बढ़ते क्रम की संख्या

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

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

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

उदाहरण(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