Algorithm (Prefix Scanning)

1. Let the input array be $A$. Note that an element $A[i]$ could be used as a splitting point if and only if $\max_{j = 0}^{i} A[j] <= \min_{j = i + 1}^{n - 1} A[j]$
2. So the problem is reduced to computing the prefix and suffix max/min of the array, which could be done in linear time.
3. Total time complexity is $O(N)$, where $N$ is the length of the array.
4. We need to add 1 to the final answer because the whole array is also counted.

Code

template <typename T> struct max_monoid {
  typedef T value_type;
  value_type unit() const { return std::numeric_limits<T>::lowest(); }
  value_type mult(value_type a, value_type b) const { return std::max(a, b); }
};

template <typename T> struct min_monoid {
  typedef T value_type;
  value_type unit() const { return std::numeric_limits<T>::max(); };
  value_type mult(value_type a, value_type b) const { return std::min(a ,b); }
};

template <typename Monoid, typename T,
          typename std::enable_if_t<std::is_same_v<T, typename Monoid::value_type>>* = nullptr>
vector<T> prefix_scan(const vector<T>& x) {
  static constexpr Monoid monoid {};
  vector<T> result(size(x), T{});
  for (int i = 0; i < size(x); ++i) {
    if (i == 0)
      result[i] = x[i];
    else
      result[i] = monoid.mult(result[i - 1], x[i]);
  }
  return result;
}

template <typename Monoid, typename T,
          typename std::enable_if_t<std::is_same_v<T, typename Monoid::value_type>>* = nullptr>
vector<T> suffix_scan(const vector<T> &x) {
  static constexpr Monoid monoid{};
  vector<T> result(size(x), T{});
  for (int i = size(x) - 1; i >= 0; --i) {
    if (i == size(x) - 1)
      result[i] = x[i];
    else
      result[i] = monoid.mult(result[i + 1], x[i]);
  }
  return result;
}

class Solution {
 public:
  int maxChunksToSorted(vector<int>& arr) {
    const auto prefix_max = prefix_scan<max_monoid<int>>(arr);
    const auto suffix_min = suffix_scan<min_monoid<int>>(arr);
    const auto solution = [&](int acc = 1) {
      for (int i = 0; i < size(arr) - 1; ++i) 
        if (prefix_max[i] <= suffix_min[i + 1])
          ++acc;
      return acc;
    }();
    return solution;
  }
};