Given a non-empty unsorted array of integers, return the maximum number of subarrays possible to divide the array into, such that sorting the array in non-descending order would keep each subarray's elements contiguous and keep the subarrays in their original order.
Example 1:
Input: nums = [2, 5, 1, 9, 7, 6]
Output: 2
Explanation:
The array, sorted, is [1, 2, 5, 6, 7, 9].
[[2, 5, 1], [9, 7, 6]] is the most that the array can be partitioned (2 subarrays) such that
- the elements of each subarray remains contiguous: [2, 5, 1] -> 1, 2, 5 | [9, 7, 6] -> 6, 7, 9
- the subarrays maintain their orderExample 2:
Input: nums = [1, 3, 3, 5, 7, 7, 9]
Output: 7
Explanation: [[1], [3], [3], [5], [7], [7], [9]]Example 3:
Input: nums = [2, 9, 3, 1, 4, 4, 5]
Output: 1Comments (3)