Maximum and Minimum Values of an Algebraic Expression | Python3 program to find the maximum and minimum values of an Algebraic expression of given form ; Finding sum of array elements ; shifting the integers by 50 so that they become positive ; dp [ i ] [ j ] represents true if sum j can be reachable by choosing i numbers ; if dp [ i ] [ j ] is true , that means it is possible to select i numbers from ( n + m ) numbers to sum upto j ; k can be at max n because the left expression has n numbers ; checking if a particular sum can be reachable by choosing n numbers ; getting the actual sum as we shifted the numbers by 50 to avoid negative indexing in array ; Driver Code
def minMaxValues ( arr , n , m ) : NEW_LINE INDENT sum = 0 NEW_LINE INF = 1000000000 NEW_LINE MAX = 50 NEW_LINE for i in range ( 0 , ( n + m ) ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE arr [ i ] += 50 NEW_LINE DEDENT dp = [ [ 0 for x in range ( MAX * MAX + 1 ) ] for y in range ( MAX + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 0 , ( n + m ) ) : NEW_LINE INDENT for k in range ( min ( n , i + 1 ) , 0 , - 1 ) : NEW_LINE INDENT for j in range ( 0 , MAX * MAX + 1 ) : NEW_LINE INDENT if ( dp [ k - 1 ] [ j ] ) : NEW_LINE INDENT dp [ k ] [ j + arr [ i ] ] = 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT max_value = - 1 * INF NEW_LINE min_value = INF NEW_LINE for i in range ( 0 , MAX * MAX + 1 ) : NEW_LINE INDENT if ( dp [ n ] [ i ] ) : NEW_LINE INDENT temp = i - 50 * n NEW_LINE max_value = max ( max_value , temp * ( sum - temp ) ) NEW_LINE min_value = min ( min_value , temp * ( sum - temp ) ) NEW_LINE DEDENT DEDENT print ( " Maximum Value : { } Minimum Value : { } " . format ( max_value , min_value ) ) NEW_LINE DEDENT n = 2 NEW_LINE m = 2 NEW_LINE arr = [ 1 , 2 , 3 , 4 ] NEW_LINE minMaxValues ( arr , n , m ) NEW_LINE