Max Chunks To Make Sorted trong C++

Cho mảng arr là hoán vị của [0, 1, ..., arr.length - 1]. Ta phải chia mảng thànhいくつか "chunks" (phân đoạn), sắp xếp từng phân đoạn riêng lẻ. Sau khi nối lại, kết quả là mảng đã sắp xếp. Tìm số lượng chunks tối đa có thể tạo.

Ví dụ: [1,0,2,3,4] → output 4, vì có thể chia thành [1,0], [2], [3], [4].

Giải thuật

• ans = 0, minVal = INF, n = arr.size(), maxVal = -INF
• Duyệt i từ 0 đến n-1:
  • maxVal = max(arr[i], maxVal)
  • Nếu maxVal == i thì ans++
• Trả về ans.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0;
        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;
    }
};

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

Input

[1,0,2,3,4]

Output

4