मान लीजिए कि हमने एक ऐरे एरर दिया है जो कि [0, 1, ..., arr.length - 1] का क्रमचय है, हमें ऐरे को कुछ संख्या में "चंक्स" में विभाजित करना होगा। "या विभाजन, और व्यक्तिगत रूप से प्रत्येक विभाजन को क्रमबद्ध करें। तो उन्हें संयोजित करने के बाद, परिणाम क्रमबद्ध सरणी होगी। तो यदि सरणी [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
- मैं के लिए 0 से n की सीमा में
- maxVal :=अधिकतम गिरफ्तारी[i] और maxVal
- यदि maxVal =i है, तो उत्तर को 1 से बढ़ा दें
- वापसी उत्तर
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#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