C++ O(n) greedy with proof
Going from left to right, if there is a number to the right that is less than the current max of the chunk or if the chunk is empty, then the next number to the
Going from left to right, if there is a number to the right that is less than the current max of the chunk or if the chunk is empty, then the next number to the right has to be included in the current chunk. Now if all the numbers to the right are at least as large as all numbers in the current chunk, then in an optimal solution, we can always split the current chunk out.\n```\nclass Solution {\npublic:\n    int maxChunksToSorted(vector<int>& a) {\n        int n = a.size();\n        vector<int> b(n);\n        b[n-1] = a[n-1];\n        for( int i = n-2; i >=0; --i) b[i] = min(a[i],b[i+1]);\n        int cnt = 1, ans = 1, mx = a[0];\n        for (int i=1; i <n;++i) {\n            if (b[i] < mx) ++cnt,mx = max(mx,a[i]);\n            else cnt = 1, ++ans, mx = a[i];\n        }\n        return ans;\n    }\n};\n```
[]