Maximum product of an increasing subsequence | Returns product of maximum product increasing subsequence . ; Initialize MPIS values ; Compute optimized MPIS values considering every element as ending element of sequence ; Pick maximum of all product values ; Driver program to test above function
< ? php function lis ( & $ arr , $ n ) { $ mpis = array_fill ( 0 , $ n , NULL ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ mpis [ $ i ] = $ arr [ $ i ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ i ; $ j ++ ) if ( $ arr [ $ i ] > $ arr [ $ j ] && $ mpis [ $ i ] < ( $ mpis [ $ j ] * $ arr [ $ i ] ) ) $ mpis [ $ i ] = $ mpis [ $ j ] * $ arr [ $ i ] ; return max ( $ mpis ) ; } $ arr = array ( 3 , 100 , 4 , 5 , 150 , 6 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo lis ( $ arr , $ n ) ; return 0 ; ? >