Description
You are given an integer array arr. We split arr into some number of chunks and individually sort each chunk. After concatenating them, the result should equal the sorted array. Return the largest number of chunks we can make.
Examples
Input:
arr = [5,4,3,2,1]Output:
1Explanation:
Cannot split; whole array is one chunk.
Input:
arr = [1,1,1,1]Output:
4Explanation:
Since all elements are identical, splitting at any position is valid. Each individual element forms a valid chunk because sorting identical elements produces no change. The maximum number of chunks equals the array length: 4.
Input:
arr = [1,4,0,2,3,5]Output:
2Explanation:
The array splits into chunks [1,4,0,2,3] and [5]. The first chunk contains elements {0,1,2,3,4} which when sorted gives [0,1,2,3,4], and the second chunk [5] stays [5]. Together they form the fully sorted array. The maximum number of chunks is 2.
Constraints
- •
1 ≤ arr.length ≤ 2000 - •
0 ≤ arr[i] ≤ 10^8