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
function findMaxVal ( arr , n , num , maxLimit ) { var ind ; var val ; var dp = Array . from ( Array ( n ) , ( ) => Array ( maxLimit + 1 ) ) ; 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 ; } var num = 1 ; var arr = [ 3 , 10 , 6 , 4 , 5 ] ; var n = arr . length ; var maxLimit = 15 ; document . write ( findMaxVal ( arr , n , num , maxLimit ) ) ;