Minimum insertions to sort an array | method returns min steps of insertion we need to perform to sort array ' arr ' ; lis [ i ] is going to store length of lis that ends with i . ; Initialize lis values for all indexes ; Compute optimized lis values in bottom up manner ; The overall LIS must end with of the array elements . Pick maximum of all lis values ; return size of array minus length of LIS as final result ; Driver code
< ? php function minInsertionStepToSortArray ( $ arr , $ N ) { $ lis [ $ N ] = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ lis [ $ i ] = 1 ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) for ( $ j = 0 ; $ j < $ i ; $ j ++ ) if ( $ arr [ $ i ] >= $ arr [ $ j ] && $ lis [ $ i ] < $ lis [ $ j ] + 1 ) $ lis [ $ i ] = $ lis [ $ j ] + 1 ; $ max = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) if ( $ max < $ lis [ $ i ] ) $ max = $ lis [ $ i ] ; return ( $ N - $ max ) ; } $ arr = array ( 2 , 3 , 5 , 1 , 4 , 7 , 6 ) ; $ N = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo minInsertionStepToSortArray ( $ arr , $ N ) ; ? >