Maximum sum increasing subsequence from a prefix and a given element after prefix is must | PHP program to find maximum sum increasing subsequence till i - th index and including k - th index . ; Initializing the first row of the dp [ ] [ ] . ; Creating the dp [ ] [ ] matrix . ; To calculate for i = 4 and k = 6. ; Driver Code
< ? php function pre_compute ( & $ a , $ n , $ index , $ k ) { $ dp = array_fill ( 0 , $ n , array_fill ( 0 , $ n , NULL ) ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ a [ $ i ] > $ a [ 0 ] ) $ dp [ 0 ] [ $ i ] = $ a [ $ i ] + $ a [ 0 ] ; else $ dp [ 0 ] [ $ i ] = $ a [ $ i ] ; } for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { if ( $ a [ $ j ] > $ a [ $ i ] && $ j > $ i ) { if ( ( $ dp [ $ i - 1 ] [ $ i ] + $ a [ $ j ] ) > $ dp [ $ i - 1 ] [ $ j ] ) $ dp [ $ i ] [ $ j ] = $ dp [ $ i - 1 ] [ $ i ] + $ a [ $ j ] ; else $ dp [ $ i ] [ $ j ] = $ dp [ $ i - 1 ] [ $ j ] ; } else $ dp [ $ i ] [ $ j ] = $ dp [ $ i - 1 ] [ $ j ] ; } } return $ dp [ $ index ] [ $ k ] ; } $ a = array ( 1 , 101 , 2 , 3 , 100 , 4 , 5 ) ; $ n = sizeof ( $ a ) ; $ index = 4 ; $ k = 6 ; echo pre_compute ( $ a , $ n , $ index , $ k ) ; ? >