Two-pass Java O(n) time/space solution
Assume the input array is arr with length n. A subarray arr[i,j] can form a chunk if it satisfies the following two conditions simultaneously:\n\n1. Its maximum
Assume the input array is `arr` with length `n`. A subarray `arr[i,j]` can form a chunk if it satisfies the following two conditions simultaneously:\n\n1. Its maximum element is no greater than the minimum element of the subarray `arr[j+1, n-1]`.\n\n2. Its minimum element is no less than the maximum element of the subarray `arr[0, i-1]`. \n\nSince we want most number of chunks, we need to find as many such subarrays as possible -- we will build the chunks in a greedy manner, either from left to right or from right to left. For the former, the second condition will be met automatically for each chunk, while for the latter, the first condition will be met automatically for each chunk. \n\nHere we will take the first option and construct the chunks from left to right. All the information we need then is the minimum elements for each of the subarrays `arr[j+1, n-1]`. In the following code, we will use `min[j]` to denote the minimum element for the subarray `arr[j+1, n-1]` (for the special case `j == n-1`, we set `min[n-1] = Integer.MAX_VALUE`). To compute `min[j]`, we can use a simple recurrence relation: `min[j] = Math.min(min[j+1], arr[j+1])`, which entails a backward iteration of the `arr` array.\n\nWe then loop through `arr` in forward direction, where for each index `j`, we check if the first condition mentioned above is satisfied, that is, if the maximum element of the subarray `arr[0, j]` (which will also be the maximum element of the current chunk being searched) is no greater than the minimum element of the subarray `arr[j+1, n-1]`. If so, a chunk is found and we increase the result count by `1`. Here is the two-pass `O(n)` time/space solution:\n\n```\npublic int maxChunksToSorted(int[] arr) {\n    int n = arr.length, res = 0;\n    \n    int[] min = new int[n];\n    min[n - 1] = Integer.MAX_VALUE;\n    \n    for (int j = n - 2; j >= 0; j--) {\n        min[j] = Math.min(min[j + 1], arr[j + 1]);\n    }\n    \n    for (int j = 0, max = Integer.MIN_VALUE; j < n; j++) {\n        max = Math.max(max, arr[j]);\n        if (max <= min[j]) res++;\n    }\n        \n    return res;\n}\n```
[]