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
< ? php function sorted_partitions ( $ arr , $ n ) { $ right_min [ $ n + 1 ] = array ( ) ; $ right_min [ $ n ] = PHP_INT_MAX ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) { $ right_min [ $ i ] = min ( $ right_min [ $ i + 1 ] , $ arr [ $ i ] ) ; } $ partitions = 0 ; for ( $ current_max = $ arr [ 0 ] , $ i = 0 ; $ i < $ n ; $ i ++ ) { $ current_max = max ( $ current_max , $ arr [ $ i ] ) ; if ( $ current_max <= $ right_min [ $ i + 1 ] ) $ partitions ++ ; } return $ partitions ; } $ arr = array ( 3 , 1 , 2 , 4 , 100 , 7 , 9 ) ; $ n = sizeof ( $ arr ) ; $ ans = sorted_partitions ( $ arr , $ n ) ; echo $ ans , " STRNEWLINE " ; ? >