Max Chunks để sắp xếp trong C ++

Giả sử chúng ta đã cho một mảng arr là hoán vị của [0, 1, ..., arr.length - 1], chúng ta phải chia mảng thành một số "khối "hoặc phân vùng và sắp xếp riêng từng phân vùng. Vì vậy, sau khi nối chúng, kết quả sẽ là mảng đã được sắp xếp. Vì vậy, nếu mảng giống như [1,0,2,3,4], thì đầu ra sẽ là 4, vì chúng ta có thể chia thành hai phân vùng như [1, 0] và [2,3,4], nhưng điều này có thể cũng đúng rằng [1, 0], [2], [3], [4]. Vì vậy, đây là số khối cao nhất có thể, vì vậy sản lượng là 4.

Số lượng nhiều nhất chúng ta có thể tạo ra là bao nhiêu?

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0, minVal:=inf, n:=size of arr và maxVal:=-inf
• cho tôi trong phạm vi từ 0 đến n
  • maxVal:=max of arr [i] và maxVal
  • nếu maxVal =i, sau đó tăng ans lên 1
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[1,0,2,3,4]

Đầu ra

4