मान लीजिए हमें एक सरणी arr दी गई है जो [0, 1, ..., arr.length - 1] का एक क्रमचय (permutation) है, हमें सरणी को कुछ संख्या में "चंक्स" या विभाजन में विभाजित करना है, और प्रत्येक विभाजन को व्यक्तिगत रूप से क्रमबद्ध करना है। इसलिए उन्हें जोड़ने के बाद, परिणाम क्रमबद्ध सरणी होगी। इसलिए यदि सरणी [1,0,2,3,4] जैसी है, तो आउटपुट 4 होगा, क्योंकि हम इसे दो विभाजन जैसे [1, 0] और [2,3,4] में विभाजित कर सकते हैं, लेकिन यह भी सच हो सकता है कि [1, 0], [2], [3], [4]। तो यह चंक्स की उच्चतम संभव संख्या है, इसलिए आउटपुट 4 है।
हम सबसे अधिक कितने चंक्स बना सकते हैं?
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ans := 0, minVal := inf, n := arr का आकार, और maxVal := -inf
- i को 0 से n तक की रेंज में
- maxVal := arr[i] और maxVal का अधिकतम
- यदि maxVal = i, तो ans को 1 से बढ़ाएं
- ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxChunksToSorted(vector<int>& arr) { int ans = 0; int minVal = INT_MAX; int n = arr.size(); int maxVal = INT_MIN; for(int i = 0; i < n; i++){ maxVal = max(arr[i], maxVal); if(maxVal == i){ ans++; } } return ans; } }; main(){ Solution ob; vector<int> v = {1,0,2,3,4}; cout << (ob.maxChunksToSorted(v)); }इनपुट
[1,0,2,3,4]
आउटपुट
4
