সি++-এ আলাদা আলাদা সর্ট করে পুরো অ্যারে সর্টেড বানানো যাবে এমন সর্বোচ্চ পার্টিশন গণনা

0 থেকে N-1 রেঞ্জের উপাদান বিশিষ্ট একটি অনসর্টেড অ্যারে দেওয়া আছে। লক্ষ্য হল অ্যারেটির সর্বোচ্চ পার্টিশন (ভাগ) বের করা যেগুলো আলাদা আলাদা সর্ট করলে পুরো অ্যারে সর্টেড হয়ে যায়।

সর্টেড অবস্থায় উপাদানটি তার ইনডেক্সের সমান হয়: Arr[i] = i। বাম পাশে সর্বোচ্চ মান (maxx) খুঁজে বের করা হয়। যখন maxx == i হয়, তখন সেটি সঠিক পজিশনে পৌঁছেছে। তার বামপাশের সব উপাদান ছোট, ডানপাশের সব বড়। তাই একটি পার্টিশন বানানো যায়। ডানপাশের বাকি উপাদানগুলোর জন্যও একই পদ্ধতি অনুসরণ করা হয়।

উদাহরণ

ইনপুট: Arr[] = { 0,3,2,1,4,5 }

আউটপুট: সর্বোচ্চ পার্টিশন: ৩

ব্যাখ্যা: ০ থেকে শুরু: max=0। ইনডেক্স ০ থেকে ৩ পর্যন্ত ৩ সর্বোচ্চ। i=3-এ maxx==i। প্রথম পার্টিশন [0,3,2,1]। ইনডেক্স ৪: max=4, i=4 → পার্টিশন [4]। ইনডেক্স ৫: max=5, i=5 → পার্টিশন [5]। মোট ৩ পার্টিশন।

ইনপুট: Arr[] = { 5,4,3,2,1,0 }

আউটপুট: সর্বোচ্চ পার্টিশন: ১

ব্যাখ্যা: ইনডেক্স ০ থেকে ৫ পর্যন্ত ৫ সর্বোচ্চ। i=5-এ maxx==i। একমাত্র পার্টিশন [5,4,3,2,1,0]।

অ্যাপ্রোচ

0 থেকে N রেঞ্জের Num[] অ্যারে।
partitions(int arr[], int n) ফাংশন অ্যারে এবং দৈর্ঘ্য গ্রহণ করে সর্বোচ্চ পার্টিশন সংখ্যা রিটার্ন করে।
count=0, maxx=arr[0]।
for i=0 থেকে n-1: arr[i]>maxx হলে maxx আপডেট। maxx==i হলে count++।

উদাহরণ কোড

#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