Build the table val [ ] in bottom up manner and return the last entry from the table
for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { $ max_val = PHP_INT_MIN ; for ( $ j = 0 ; $ j < $ i ; $ j ++ ) $ max_val = max ( $ max_val , $ price [ $ j ] + $ val [ $ i - $ j - 1 ] ) ; $ val [ $ i ] = $ max_val ; } return $ val [ $ n ] ; }