हमें N संख्याओं की एक सरणी दी गई है जिसमें तत्व 0 और N-1 श्रेणी में हैं। तत्व अवर्गीकृत हैं। लक्ष्य सरणी के विभाजन की अधिकतम संख्या को खोजना है जिसे व्यक्तिगत रूप से क्रमबद्ध किया जा सकता है और फिर लंबाई एन की एक पूरी क्रमबद्ध सरणी बनाने के लिए संयोजित किया जा सकता है।
प्रत्येक विभाजन को इस प्रकार चुना जाता है कि उसमें मौजूद तत्वों को क्रमबद्ध न किया जाए। 0 और N-1 के बीच की N संख्याओं के लिए, सॉर्ट किए गए तत्व मान के बराबर इंडेक्स पर होते हैं। Arr[i] =i.
हम प्रत्येक तत्व की उसके बाईं ओर अब तक पाए गए अधिकतम मान से तुलना करके इसे हल करेंगे। अधिकतम की सही स्थिति पर पहुंचने पर, (अधिकतम ==i)। इसके बाईं ओर के सभी तत्व कम हैं इसलिए एक अलग विभाजन बना सकते हैं। इसके दाईं ओर सभी बड़े हैं। अब बाकी सही तत्वों के लिए भी यही प्रक्रिया करें और उन्हें विभाजनों में विभाजित करें।
आइए उदाहरणों से समझते हैं।
इनपुट - अरे [] ={ 0,3,2,1,4,5 }
आउटपुट - विभाजनों की अधिकतम संख्या - 3
स्पष्टीकरण − 0 से शुरू होकर, चलो max=0 Arr[0]
सूचकांक 0 और 3 के बीच अधिकतम है। जब सूचकांक i=3 ( maxx==i) पर पहुंच गया। तो पहला विभाजन है [0,3,2,1]
अनुक्रमणिका 4 के लिए, अधिकतम 4 है। अनुक्रमणिका i=4 ( maxx==i)। तो दूसरा विभाजन है [4]
अनुक्रमणिका 5 के लिए, अधिकतम 5 है। अनुक्रमणिका i=5 ( maxx==i)। तो दूसरा विभाजन है [5]
कुल 3 विभाजन [0,3,2,1] [4] [5]। प्रत्येक को क्रमबद्ध करें और संयोजित करें।
इनपुट − Arr[]={ 5,4,3,2,1,0 }
आउटपुट - विभाजनों की अधिकतम संख्या - 1
स्पष्टीकरण − 0 से शुरू होकर, चलो max=0 Arr[0]
सूचकांक 0 और 5 के बीच अधिकतम 5 है। सूचकांक i=5 ( maxx==i) पर पहुंचने पर। तो केवल विभाजन है [5,4,3,2,1,0]
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
हम एक पूर्णांक सरणी संख्या [] लेते हैं जो 0 से एन तक की संख्या के साथ प्रारंभ होती है।
-
फ़ंक्शन विभाजन (int arr[], int n ) एक सरणी और उसकी लंबाई को पैरामीटर के रूप में लेता है और अधिकतम विभाजन की गिनती देता है जिसे पूरे सरणी को क्रमबद्ध करने के लिए व्यक्तिगत रूप से सॉर्ट किया जा सकता है।
-
आरंभिक विभाजन संख्या 0 है। प्रारंभिक अधिकतम मान अधिकतम में गिरफ्तारी [0] के रूप में है।
-
सबसे बाएं तत्व से शुरू होने वाले सभी तत्वों के लिए। पता लगाएं कि यह मैक्स से बड़ा है या नहीं।
-
अगर arr[i]>maxx सच है। अधिकतम अपडेट करें।
-
यदि वर्तमान अधिकतम और सूचकांक समान है। ( maxx==i ) तो i तक के सभी तत्व एक विभाजन का हिस्सा हैं। वेतन वृद्धि की संख्या।
-
ऐसा बाकी तत्वों के लिए दाईं ओर अंत तक करें।
-
परिणाम को गिनती के रूप में लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int partitions(int arr[], int n){
int count = 0;
int maxx = arr[0];
for (int i = 0; i < n; ++i) {
if(arr[i] > maxx)
maxx=arr[i];
if (maxx == i)
count++;
}
return count;
}
int main(){
int Num[] = { 2,1,0,4,5,3 };
int len = 6;
cout <<"Maximum partitions that can be sorted: "<<partitions(Num, len);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Maximum partitions that can be sorted: 18