Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1631
You are given an algebraic expression of the form (x1 + x2 + x3 + . . . + xn) ∗ (y1 + y2 + . . . + ym) and (n + m) integers. You have to find the maximum and minimum value of the expression using the given integers. For example if you are given (x1 + x2) ∗ (y1 + y2) and you are given 1, 2, 3 and 4. Then maximum value is (1 + 4) ∗ (2 + 3) = 25 where as minimum value is (4 + 3) ∗ (2 + 1) = 21. Input Each input set starts with two positive integers N, M (< 51). Next line follows (N +M) integers which are in the range of −50 to 50. Input is terminated by end of file. There will be atmost 110 testcases. Output Output is one line for each case, maximum value followed by minimum value.
Sample Input 2 2 1 2 3 4 3 1 1 2 3 4 2 2 2 2 2 2
Sample Output 25 21 24 9 16 16
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m,v;
while(scanf("%d %d",&n,&m) != EOF){
vector<int> nums;
if(m<n) swap(n,m);
int sum = 0;
for(int i=0;i < (n+m);i++){
scanf("%d",&v);
nums.push_back(v+50);
sum += nums.back(>;
}
vector < vector<bool>> dp(n+1,vector < bool>(sum+1));
dp[0][0] = true;
// foreach num, foreach subset size, foreach sum
for(int i=0;i < nums.size();i++) // num state first to avoid duplicate
for(int j=n-1;j>=0;j--) // larger j first, because can only use this number once
for(int k=nums[i];k < =sum;k++)
if(dp[j][k-nums[i]])
dp[j+1][k] = true;
int maximum = INT_MIN, minimum = INT_MAX;
for(int i=0;i<=sum;i++)
if(dp[n][i]){
int sum_n = i+(-50*n);
int sum_m = sum-i+(-50*m);
int prod = sum_n * sum_m;
maximum = max(prod,maximum);
minimum = min(prod,minimum);
}
printf("%d %d\n",maximum,minimum>;
}
}
.Input
1 2 3 4
3 1
1 2 3 4
2 2
2 2 2 2
Output
24 9
16 16
Demonstration
UVA Online Judge solution - 10690-Expression Again - UVA Online Judge solution in C,C++,java