C++ में मैक्स चंक्स टू मेक सॉर्टेड II (Max Chunks To Make Sorted II)

समस्या विवरण

हमें एक पूर्णांक सरणी arr दी गई है। हमें सरणी को कुछ पार्टीशन (partitions) में विभाजित करना है, प्रत्येक पार्टीशन को व्यक्तिगत रूप से क्रमबद्ध (sort) करना है, और फिर उन्हें जोड़कर (concatenate) एक क्रमबद्ध सरणी प्राप्त करनी है। हमें अधिकतम संभव पार्टीशन की संख्या ज्ञात करनी है।

उदाहरण

इनपुट

[3,2,4,5,5]

आउटपुट

4

व्याख्या

हम पार्टीशन बना सकते हैं: [3,2], [4], [5], [5]। प्रत्येक को क्रमबद्ध करने पर: [2,3], [4], [5], [5]। जोड़ने पर: [2,3,4,5,5] जो क्रमबद्ध है।

समाधान दृष्टिकोण

प्रीफिक्स मैक्सिमम (prefix maximum) और सफिक्स मिनिमम (suffix minimum) सरणियों का उपयोग करें:

1. maxOfLeft[i] = सूचकांक 0 से i तक का अधिकतम मान।
2. minOfRight[i] = सूचकांक i से n-1 तक का न्यूनतम मान।
3. यदि minOfRight[i+1] >= maxOfLeft[i], तो i के बाद पार्टीशन बना सकते हैं।
4. ऐसे सभी वैध पार्टीशन बिंदुओं की गणना करें + 1 (अंतिम पार्टीशन के लिए)।

कार्यकारी प्रोग्राम

#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);
    return 0;
}

आउटपुट

4