JAVA O(n) solution, easy to understand
Max[i] is the max from begining to i (0 to i)\nMin[i] is the min from last to i (arr.length-1 to i)\ni can be a dividing point whenever max[i]<=min[i+1], don\'t
Max[i] is the max from begining to i (0 to i)\nMin[i] is the min from last to i (arr.length-1 to i)\ni can be a dividing point whenever max[i]<=min[i+1], don\'t forget to add 1 to the last element since last element can always be a diving point.\n\nHere are the code:\n\n\n    public int maxChunksToSorted(int[] arr) {\n        int[] max = new int[arr.length];\n        int[] min = new int[arr.length];\n        max[0]=arr[0];\n        min[arr.length-1]=arr[arr.length-1];\n        for (int i=1;i<arr.length;i++) {\n            max[i]=Math.max(max[i-1], arr[i]);\n        }\n        for (int i=arr.length-2;i>=0;i--) {\n            min[i] = Math.min(min[i+1], arr[i]);\n        }\n        \n        int count=0;\n        for (int i=0;i<arr.length;i++) {\n            if (i<arr.length-1&&max[i]<=min[i+1]) {\n                count++;\n            } \n        }\n        return ++count;\n    }
[]