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
def findMaxVal ( arr , n , num , maxLimit ) : NEW_LINE INDENT ind = - 1 ; NEW_LINE val = - 1 ; NEW_LINE dp = [ [ 0 for i in range ( maxLimit + 1 ) ] for j in range ( n ) ] ; NEW_LINE for ind in range ( n ) : NEW_LINE INDENT for val in range ( maxLimit + 1 ) : NEW_LINE INDENT if ( ind == 0 ) : NEW_LINE INDENT if ( num - arr [ ind ] == val or num + arr [ ind ] == val ) : NEW_LINE INDENT dp [ ind ] [ val ] = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ ind ] [ val ] = 0 ; NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( val - arr [ ind ] >= 0 and val + arr [ ind ] <= maxLimit ) : NEW_LINE INDENT if ( dp [ ind - 1 ] [ val - arr [ ind ] ] == 1 or dp [ ind - 1 ] [ val + arr [ ind ] ] == 1 ) : NEW_LINE INDENT dp [ ind ] [ val ] = 1 ; NEW_LINE DEDENT DEDENT elif ( val - arr [ ind ] >= 0 ) : NEW_LINE INDENT dp [ ind ] [ val ] = dp [ ind - 1 ] [ val - arr [ ind ] ] ; NEW_LINE DEDENT elif ( val + arr [ ind ] <= maxLimit ) : NEW_LINE INDENT dp [ ind ] [ val ] = dp [ ind - 1 ] [ val + arr [ ind ] ] ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ ind ] [ val ] = 0 ; NEW_LINE DEDENT DEDENT DEDENT DEDENT for val in range ( maxLimit , - 1 , - 1 ) : NEW_LINE INDENT if ( dp [ n - 1 ] [ val ] == 1 ) : NEW_LINE INDENT return val ; NEW_LINE DEDENT DEDENT return - 1 ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT num = 1 ; NEW_LINE arr = [ 3 , 10 , 6 , 4 , 5 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE maxLimit = 15 ; NEW_LINE print ( findMaxVal ( arr , n , num , maxLimit ) ) ; NEW_LINE DEDENT