Maximize array elements upto given number | Function to find maximum possible value of number that can be obtained using array elements . ; Variable to represent current index . ; Variable to show value between 0 and maxLimit . ; Table to store whether a value can be obtained or not upto a certain index . 1. dp [ i ] [ j ] = 1 if value j can be obtained upto index i . 2. dp [ i ] [ j ] = 0 if value j cannot be obtained upto index i . ; Check for index 0 if given value val can be obtained by either adding to or subtracting arr [ 0 ] from num . ; 1. If arr [ ind ] is added to obtain given val then val - arr [ ind ] should be obtainable from index ind - 1. 2. If arr [ ind ] is subtracted to obtain given val then val + arr [ ind ] should be obtainable from index ind - 1. Check for both the conditions . ; If either of one condition is true , then val is obtainable at index ind . ; Find maximum value that is obtained at index n - 1. ; If no solution exists return - 1. ; Driver Code
< ? php function findMaxVal ( $ arr , $ n , $ num , $ maxLimit ) { $ ind ; $ val ; $ dp [ $ n ] [ $ maxLimit + 1 ] = array ( ) ; for ( $ ind = 0 ; $ ind < $ n ; $ ind ++ ) { for ( $ val = 0 ; $ val <= $ maxLimit ; $ val ++ ) { if ( $ ind == 0 ) { if ( $ num - $ arr [ $ ind ] == $ val $ num + $ arr [ $ ind ] == $ val ) { $ dp [ $ ind ] [ $ val ] = 1 ; } else { $ dp [ $ ind ] [ $ val ] = 0 ; } } else { if ( $ val - $ arr [ $ ind ] >= 0 && $ val + $ arr [ $ ind ] <= $ maxLimit ) { $ dp [ $ ind ] [ $ val ] = $ dp [ $ ind - 1 ] [ $ val - $ arr [ $ ind ] ] || $ dp [ $ ind - 1 ] [ $ val + $ arr [ $ ind ] ] ; } else if ( $ val - $ arr [ $ ind ] >= 0 ) { $ dp [ $ ind ] [ $ val ] = $ dp [ $ ind - 1 ] [ $ val - $ arr [ $ ind ] ] ; } else if ( $ val + $ arr [ $ ind ] <= $ maxLimit ) { $ dp [ $ ind ] [ $ val ] = $ dp [ $ ind - 1 ] [ $ val + $ arr [ $ ind ] ] ; } else { $ dp [ $ ind ] [ $ val ] = 0 ; } } } } for ( $ val = $ maxLimit ; $ val >= 0 ; $ val -- ) { if ( $ dp [ $ n - 1 ] [ $ val ] ) { return $ val ; } } return -1 ; } $ num = 1 ; $ arr = array ( 3 , 10 , 6 , 4 , 5 ) ; $ n = sizeof ( $ arr ) ; $ maxLimit = 15 ; echo findMaxVal ( $ arr , $ n , $ num , $ maxLimit ) ; ? >