C++에서 정렬할 최대 청크

[0, 1, ..., arr.length - 1]의 순열인 배열 arr을 제공했다고 가정하면 배열을 몇 개의 "청크로 분할해야 합니다. " 또는 파티션을 선택하고 각 파티션을 개별적으로 정렬합니다. 따라서 그것들을 연결한 후 결과는 정렬된 배열이 됩니다. 따라서 배열이 [1,0,2,3,4]와 같으면 [1, 0] 및 [2,3,4]와 같은 두 개의 파티션으로 분할할 수 있으므로 출력은 4가 됩니다. [1, 0], [2], [3], [4]도 마찬가지입니다. 따라서 이것은 가능한 가장 많은 청크 수이므로 출력은 4입니다.

우리가 만들 수 있는 가장 많은 청크는 몇 개입니까?

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=0, minVal :=inf, n :=arr의 크기, maxVal :=-inf
0~n
- maxVal :=arr[i] 및 maxVal의 최대값
- maxVal =i이면 ans를 1만큼 증가
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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

입력

[1,0,2,3,4]