C++-এ সর্টেড অ্যারে তৈরির জন্য সর্বোচ্চ চাঙ্ক (Max Chunks To Make Sorted II) বের করা

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

উদাহরণ

ইনপুট: [3,2,4,5,5] → আউটপুট: 4

ব্যাখ্যা: পার্টিশনগুলো হতে পারে [3,2], [4], [5], [5]।

সমাধানের ধাপসমূহ

maxOfLeft[i] = সূচক i পর্যন্ত বাম পাশের সর্বোচ্চ মান।
minOfRight[i] = সূচক i থেকে ডান পাশের সর্বনিম্ন মান।
যদি minOfRight[i+1] >= maxOfLeft[i] হয়, তবে i-এর পর একটি পার্টিশন করা যায়।
এই শর্ত পূরণ করে সর্বোচ্চ পার্টিশন গণনা করুন।

প্রোগ্রাম উদাহরণ

#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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,2,4,5,5};
    cout << (ob.maxChunksToSorted(v));
}

ইনপুট

{3,2,4,5,5}