จำนวนชั่นกสูงสุดเพื่อจัดเรียง II ใน C++

สมมติว่าเรามีอาร์เรย์ arr ของจำนวนเต็ม เราต้องแบ่งอาร์เรย์เป็นชั่นก (partitions) จำนวนหนึ่ง แล้วจัดเรียงแต่ละชั่นกแยกกัน หลังจากต่อกันจะได้อาร์เรย์ที่จัดเรียงแล้ว เราต้องหาจำนวนชั่นกสูงสุดที่ทำได้

เช่น [3,2,4,5,5] เอาต์พุตคือ 4 เพราะแบ่งได้ [3,2], [4], [5], [5]

วิธีแก้ − คำนวณ maxOfLeft และ minOfRight แล้วนับจุดที่ minOfRight[i+1] >= maxOfLeft[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), 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}