O(n) -->TIME COMPLEXITY, PREFIX_MAXIMUM AND SUFFIX_MINIMUM
IntuitionTo split the array into the maximum number of chunks such that each chunk, when sorted individually and concatenated, results in a fully sorted array,
# Intuition
To split the array into the maximum number of chunks such that each chunk, when sorted individually and concatenated, results in a fully sorted array, we need to identify partition points. The key insight is that the maximum element on the left of a partition must be less than or equal to the minimum element on the right of the partition.

# Approach
1. **Prefix Maximum Array**: Create an array pfxMax where each element represents the maximum value from the start of the array to the current index.

2. **Suffix Minimum Array**: Create an array sfxMin where each element represents the minimum value from the current index to the end of the array.

3. **Partition Check**: For every possible partition point, check if the maximum value in the left partition (pfxMax[i-1]) is less than or equal to the minimum value in the right partition (sfxMin[i]). If true, increment the chunk count.


# Complexity
- Time complexity: **O(n)**

Calculating the prefix maximum and suffix minimum arrays takes O(n), and iterating over the array to count chunks also takes O(n).

- Space complexity: **O(n)**

Two additional arrays (pfxMax and sfxMin) are used, each of size 𝑛.

# Code
```cpp []
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        vector<long long> pfxMax(n), sfxMin(n); 

        pfxMax[0] = arr[0];
        for (int i = 1; i < n; ++i) {
            pfxMax[i] = max(pfxMax[i - 1], 1LL * arr[i]);
        }
        sfxMin[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            sfxMin[i] = min(sfxMin[i + 1], 1LL * arr[i]);
        }

        int chunk = 0;
        for (int i = 0; i < n; ++i) {
            long long pfxMx = (i > 0 ? pfxMax[i - 1] : -1);
            long long sfxMn = sfxMin[i];

            if (pfxMx <= sfxMn) {
                chunk += 1;
            }
        }
        return chunk;
    }
};
```
['Greedy', 'C++']