আমাদের 0 এবং N-1 রেঞ্জে থাকা উপাদানগুলির সাথে N সংখ্যার একটি অ্যারে দেওয়া হয়েছে৷ উপাদানগুলি সাজানো হয় না। লক্ষ্য হল অ্যারের সর্বাধিক সংখ্যক পার্টিশন খুঁজে বের করা যা পৃথকভাবে সাজানো যেতে পারে এবং তারপর দৈর্ঘ্যের সম্পূর্ণ সাজানো অ্যারে তৈরি করতে একত্রিত করা যেতে পারে।
প্রতিটি পার্টিশন এমনভাবে বেছে নেওয়া হয়েছে যাতে এর উপাদানগুলি সাজানো না হয়। 0 এবং N-1 এর মধ্যে থাকা N সংখ্যাগুলির জন্য, সাজানো উপাদানগুলি মানের সমান সূচকে থাকে। Arr[i] =i.
আমরা প্রতিটি উপাদানের বাম দিকে এ পর্যন্ত পাওয়া সর্বোচ্চ মানের সাথে তুলনা করে এটি সমাধান করব। সর্বাধিক সঠিক অবস্থানে পৌঁছালে, (সর্বোচ্চ ==i)। এর বাম দিকের সমস্ত উপাদান কম তাই একটি পৃথক পার্টিশন তৈরি করতে পারে। তার ডান দিকে সব বড়. এখন বাকি সঠিক উপাদানগুলির জন্য একই পদ্ধতি করুন এবং তাদের পার্টিশনে ভাগ করুন।
উদাহরণ দিয়ে বোঝা যাক।
ইনপুট − Arr[]={ 0,3,2,1,4,5 }
আউটপুট − সর্বাধিক সংখ্যক পার্টিশন − 3
ব্যাখ্যা − 0 থেকে শুরু করে, চলুন max=0 Arr[0]
সূচক 0 এবং 3. 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]
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
আমরা একটি পূর্ণসংখ্যার বিন্যাস নিই Num[] 0 থেকে N রেঞ্জের মধ্যে সংখ্যা সহ শুরু।
-
ফাংশন পার্টিশন (int arr[], int n ) প্যারামিটার হিসাবে একটি অ্যারে এবং এর দৈর্ঘ্য নেয় এবং সর্বাধিক পার্টিশনের গণনা প্রদান করে যা সম্পূর্ণ অ্যারে সাজানোর জন্য পৃথকভাবে সাজানো যেতে পারে।
-
প্রারম্ভিক পার্টিশনের সংখ্যা হল 0। প্রারম্ভিক সর্বোচ্চ মান হল maxx as arr[0]।
-
বামদিকের উপাদান থেকে শুরু করে সমস্ত উপাদানের জন্য। এটি maxx থেকে বড় কিনা তা খুঁজুন৷
৷ -
যদি 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
