C++ এ বাছাই করা II করার জন্য সর্বোচ্চ খণ্ডগুলি

ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারের অ্যারে আছে, আমাদের অ্যারেটিকে কয়েকটি পার্টিশনে বিভক্ত করতে হবে এবং প্রতিটি পার্টিশনকে পৃথকভাবে সাজাতে হবে। এখন তাদের একত্রিত করার পরে আমরা একটি সাজানো অ্যারে পাব। আমাদের খুঁজে বের করতে হবে সর্বোচ্চ কতগুলো পার্টিশন আমরা তৈরি করতে পারতাম?

সুতরাং, যদি ইনপুটটি [3,2,4,5,5] এর মত হয়, তাহলে আউটপুট 4 হবে, যেমন আমরা [3,2], [4], [5], [5] এর মতো পার্টিশন তৈরি করতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

cnt :=1
n :=arr এর আকার
n
আকারের একটি অ্যারে maxOfLeft সংজ্ঞায়িত করুন
n
আকারের একটি অ্যারে minOfRight সংজ্ঞায়িত করুন
maxOfLeft[0] :=arr[0]
আরম্ভ করার জন্য i :=1, যখন i
- maxOfLeft[i] :=সর্বাধিক maxOfLeft[i - 1] এবং arr[i]
minOfRight[n - 1] =arr[n - 1]
আরম্ভ করার জন্য i :=n - 2, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
- minOfRight[i] :=সর্বনিম্ন minOfRight[i + 1] এবং arr[i]
আরম্ভ করার জন্য i :=0, যখন i
- যদি minOfRight[i + 1]>=maxOfLeft[i] হয়, তাহলে −
  - (1 দ্বারা cnt বাড়ান)
ফেরত cnt

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxChunksToSorted(vector<int>& arr) {
      int cnt = 1;
      int n = arr.size();
      vector<int> maxOfLeft(n);
      vector<int> minOfRight(n);
      maxOfLeft[0] = arr[0];
      for (int i = 1; i < n; i++)
         maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
         minOfRight[n - 1] = arr[n - 1];
      for (int i = n - 2; i >= 0; i--)
         minOfRight[i] = min(minOfRight[i + 1], arr[i]);
      for (int i = 0; i < n - 1; i++) {
         if (minOfRight[i + 1] >= maxOfLeft[i])
         cnt++;
      }
      return cnt;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,5,5};
   cout << (ob.maxChunksToSorted(v));
}

ইনপুট

{3,2,4,5,5}