Maximum number of partitions that can be sorted individually to make sorted | Function to find maximum partitions . ; Find maximum in prefix arr [ 0. . i ] ; If maximum so far is equal to index , we can make a new partition ending at index i . ; Driver code
< ? php function maxPartitions ( $ arr , $ n ) { $ ans = 0 ; $ max_so_far = 0 ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) { $ max_so_far = max ( $ max_so_far , $ arr [ $ i ] ) ; if ( $ max_so_far == $ i ) $ ans ++ ; } return $ ans ; } { $ arr = array ( 1 , 0 , 2 , 3 , 4 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo maxPartitions ( $ arr , $ n ) ; return 0 ; } ? >