Partition an array such into maximum increasing segments | Returns the maximum number of sorted subarrays in a valid partition ; Find minimum value from right for every index ; Finding the shortest prefix such that all the elements in the prefix are less than or equal to the elements in the rest of the array . ; if current max is less than the right prefix min , we increase number of partitions . ; Driver Code ; Find minimum value from right for every index
function sorted_partitions ( arr ) { let n = arr . length ; let right_min = new Array ( n + 1 ) ; right_min . fill ( 0 ) ; right_min [ n ] = Number . MAX_VALUE ; for ( let i = n - 1 ; i >= 0 ; i -- ) { right_min [ i ] = Math . min ( right_min [ i + 1 ] , arr [ i ] ) ; } let partitions = 0 ; for ( let current_max = arr [ 0 ] , i = 0 ; i < n ; i ++ ) { current_max = Math . max ( current_max , arr [ i ] ) ; if ( current_max <= right_min [ i + 1 ] ) partitions ++ ; } return partitions ; } let arr = [ 3 , 1 , 2 , 4 , 100 , 7 , 9 ] ; let ans = sorted_partitions ( arr ) ; document . write ( ans ) ;