# 可以單獨排序以進行排序的最大分區數 > 原文： [https://www.geeksforgeeks.org/maximum-number-partitions-can-sorted-individually-make-sorted/](https://www.geeksforgeeks.org/maximum-number-partitions-can-sorted-individually-make-sorted/) 給定大小為 n 的數組 arr []，以使 arr []的元素在[0，1，..n-1]范圍內，其中每個數字最多出現一次。 我們的任務是將數組劃分為可以單獨排序的最大分區數，然后進行連接以對整個數組進行排序。 **示例**： ``` Input : arr[] = [2, 1, 0, 3] Output : 2 If divide arr[] into two partitions {2, 1, 0} and {3}, sort then and concatenate then, we get the whole array sorted. Input : arr[] = [2, 1, 0, 3, 4, 5] Output : 4 The maximum number of partitions are four, we get these partitions as {2, 1, 0}, {3}, {4} and {5} ``` 這個想法基于這樣一個事實，即如果 i 處的元素最大為前綴 arr [0..i]，那么我們可以創建一個以 i 結尾的分區。 ## C++ ```cpp // CPP program to find Maximum number of partitions // such that we can get a sorted array. #include <bits/stdc++.h> using namespace std; // Function to find maximum partitions. int maxPartitions(int arr[], int n) { ????int ans = 0, max_so_far = 0; ????for (int i = 0; i < n; ++i) { ????????// Find maximum in prefix arr[0..i] ????????max_so_far = max(max_so_far, arr[i]); ????????// If maximum so far is equal to index, ????????// we can make a new partition ending at ????????// index i. ????????if (max_so_far == i) ????????????ans++; ????} ????return ans; } // Driver code int main() { ????int arr[] = { 1, 0, 2, 3, 4 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << maxPartitions(arr, n); ????return 0; } ```