मान लीजिए हमारे पास पूर्णांकों की एक अक्रमबद्ध सरणी है। हमें सबसे लंबी बढ़ती उपअनुक्रम (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] का अधिकतम
- यदि nums[i] > nums[j], तो
- j को 0 से i - 1 तक की रेंज में
- 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