Maximum and Minimum Values of an Algebraic Expression | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define INF  1e9 NEW_LINE #define MAX  50 NEW_LINE int minMaxValues ( int arr [ ] , int n , int m ) { int sum = 0 ; for ( int i = 0 ; i < ( n + m ) ; i ++ ) { sum += arr [ i ] ; arr [ i ] += 50 ; } bool dp [ MAX + 1 ] [ MAX * MAX + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i < ( n + m ) ; i ++ ) { for ( int k = min ( n , i + 1 ) ; k >= 1 ; k -- ) { for ( int j = 0 ; j < MAX * MAX + 1 ; j ++ ) { if ( dp [ k - 1 ] [ j ] ) dp [ k ] [ j + arr [ i ] ] = 1 ; } } } int max_value = - INF , min_value = INF ; for ( int i = 0 ; i < MAX * MAX + 1 ; i ++ ) { if ( dp [ n ] [ i ] ) { int temp = i - 50 * n ; max_value = max ( max_value , temp * ( sum - temp ) ) ; min_value = min ( min_value , temp * ( sum - temp ) ) ; } } cout << " Maximum ▁ Value : ▁ " << max_value << " STRNEWLINE " << " Minimum ▁ Value : ▁ " << min_value << endl ; } int main ( ) { int n = 2 , m = 2 ; int arr [ ] = { 1 , 2 , 3 , 4 } ; minMaxValues ( arr , n , m ) ; return 0 ; }