Maximum Sum Increasing Subsequence | DP | maxSumIS ( ) returns the maximum sum of increasing subsequence in arr [ ] of size n ; Initialize msis values for all indexes ; Compute maximum sum values in bottom up manner ; Pick maximum of all msis values ; Driver Code
< ? php function maxSumIS ( $ arr , $ n ) { $ max = 0 ; $ msis = array ( $ n ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ msis [ $ i ] = $ arr [ $ i ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ i ; $ j ++ ) if ( $ arr [ $ i ] > $ arr [ $ j ] && $ msis [ $ i ] < $ msis [ $ j ] + $ arr [ $ i ] ) $ msis [ $ i ] = $ msis [ $ j ] + $ arr [ $ i ] ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ max < $ msis [ $ i ] ) $ max = $ msis [ $ i ] ; return $ max ; } $ arr = array ( 1 , 101 , 2 , 3 , 100 , 4 , 5 ) ; $ n = count ( $ arr ) ; echo " Sum ▁ of ▁ maximum ▁ sum ▁ increasing ▁ subsequence ▁ is ▁ " . maxSumIS ( $ arr , $ n ) ; ? >