Dada una expresión algebraica de la forma (x 1 + x 2 + x 3 + . . . + x n ) * (y 1 + y 2 + . . . + y m ) y
(n + m) números enteros. Encuentra el valor máximo y mínimo de la expresión usando los
enteros dados.
Restricción:
n <= 50
m <= 50
-50 <= x1, x2, .. x n <= 50
Ejemplos:
Input : n = 2, m = 2
arr[] = {1, 2, 3, 4}
Output : Maximum : 25
Minimum : 21
The expression is (x1 + x2) * (y1 + y2) and
the given integers are 1, 2, 3 and 4. Then
maximum value is (1 + 4) * (2 + 3) = 25
whereas minimum value is (4 + 3) * (2 + 1)
= 21.
Input : n = 3, m = 1
arr[] = {1, 2, 3, 4}
Output : Maximum : 24
Minimum : 9
Una solución simple es considerar todas las combinaciones posibles de n números y m números restantes y calcular sus valores, a partir de los cuales se pueden derivar el valor máximo y el valor mínimo.
A continuación se muestra una solución eficiente .
La idea se basa en valores limitados de n, m, x1, x2, .. y1, y2, .. Supongamos que S es la suma de todos los (n + m) números en la expresión y que X es la suma de los n números a la izquierda de la expresión. Obviamente, la suma de los m números a la derecha de la expresión se representará como (S – X). Puede haber muchos valores posibles de X a partir de los números dados (n + m) y, por lo tanto, el problema se reduce a simplemente iterar a través de todos los valores de X y realizar un seguimiento del valor mínimo y máximo de X * (S – X).
Ahora, el problema es equivalente a encontrar todos los valores posibles de X. Como los números dados están en el rango de -50 a 50 y el valor máximo de (n + m) es 100, X estará entre -2500 y 2500, lo cual da como resultado un total de 5000 valores de X. Usaremos un enfoque de programación dinámica para resolver este problema. Considere una array dp[i][j] que puede valer 1 o 0, donde 1 significa que X puede ser igual a j eligiendo i números de los números (n + m) y 0 de lo contrario. Entonces, para cada número k, si dp[i][j] es 1, entonces dp[i + 1][j + k] también es 1 donde k pertenece a (n + m) números dados. Por lo tanto, al iterar a través de todos los k, podemos determinar si se puede alcanzar un valor de X eligiendo un total de n números.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find the maximum
// and minimum values of an Algebraic
// expression of given form
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 50
int minMaxValues(int arr[], int n, int m)
{
// Finding sum of array elements
int sum = 0;
for (int i = 0; i < (n + m); i++) {
sum += arr[i];
// shifting the integers by 50
// so that they become positive
arr[i] += 50;
}
// dp[i][j] represents true if sum
// j can be reachable by choosing
// i numbers
bool dp[MAX+1][MAX * MAX + 1];
// initialize the dp array to 01
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
// if dp[i][j] is true, that means
// it is possible to select i numbers
// from (n + m) numbers to sum upto j
for (int i = 0; i < (n + m); i++) {
// k can be at max n because the
// left expression has n numbers
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++) {
// checking if a particular sum
// can be reachable by choosing
// n numbers
if (dp[n][i]) {
// getting the actual sum as
// we shifted the numbers by
/// 50 to avoid negative indexing
// in array
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
<< "\n"
<< "Minimum Value: "
<< min_value << endl;
}
// Driver Code
int main()
{
int n = 2, m = 2;
int arr[] = { 1, 2, 3, 4 };
minMaxValues(arr, n, m);
return 0;
}
Java
// Java program to find the maximum
// and minimum values of an Algebraic
// expression of given form
import java.io.*;
import java.lang.*;
public class GFG {
static double INF = 1e9;
static int MAX = 50;
static void minMaxValues(int []arr,
int n, int m)
{
// Finding sum of array elements
int sum = 0;
for (int i = 0; i < (n + m); i++)
{
sum += arr[i];
// shifting the integers by 50
// so that they become positive
arr[i] += 50;
}
// dp[i][j] represents true if sum
// j can be reachable by choosing
// i numbers
boolean dp[][] =
new boolean[MAX+1][MAX * MAX + 1];
dp[0][0] = true;
// if dp[i][j] is true, that means
// it is possible to select i numbers
// from (n + m) numbers to sum upto j
for (int i = 0; i < (n + m); i++) {
// k can be at max n because the
// left expression has n numbers
for (int k = Math.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]] = true;
}
}
}
double max_value = -1 * INF, min_value = INF;
for (int i = 0; i < MAX * MAX + 1; i++)
{
// checking if a particular sum
// can be reachable by choosing
// n numbers
if (dp[n][i]) {
// getting the actual sum as
// we shifted the numbers by
/// 50 to avoid negative indexing
// in array
int temp = i - 50 * n;
max_value = Math.max(max_value, temp *
(sum - temp));
min_value = Math.min(min_value, temp *
(sum - temp));
}
}
System.out.print("Maximum Value: " +
(int)max_value + "\n" +
"Minimum Value: " + (int)min_value + "\n");
}
// Driver Code
public static void main(String args[])
{
int n = 2, m = 2;
int []arr = { 1, 2, 3, 4 };
minMaxValues(arr, n, m);
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
Python3
# Python3 program to find the
# maximum and minimum values
# of an Algebraic expression
# of given form
def minMaxValues(arr, n, m) :
# Finding sum of
# array elements
sum = 0
INF = 1000000000
MAX = 50
for i in range(0, (n + m)) :
sum += arr[i]
# shifting the integers by 50
# so that they become positive
arr[i] += 50
# dp[i][j] represents true
# if sum j can be reachable
# by choosing i numbers
dp = [[0 for x in range(MAX * MAX + 1)]
for y in range( MAX + 1)]
dp[0][0] = 1
# if dp[i][j] is true, that
# means it is possible to
# select i numbers from (n + m)
# numbers to sum upto j
for i in range(0, (n + m)) :
# k can be at max n because the
# left expression has n numbers
for k in range(min(n, i + 1), 0, -1) :
for j in range(0, MAX * MAX + 1) :
if (dp[k - 1][j]) :
dp[k][j + arr[i]] = 1
max_value = -1 * INF
min_value = INF
for i in range(0, MAX * MAX + 1) :
# checking if a particular
# sum can be reachable by
# choosing n numbers
if (dp[n][i]) :
# getting the actual sum
# as we shifted the numbers
# by 50 to avoid negative
# indexing in array
temp = i - 50 * n
max_value = max(max_value,
temp * (sum - temp))
min_value = min(min_value,
temp * (sum - temp))
print ("Maximum Value: {}\nMinimum Value: {}"
.format(max_value, min_value))
# Driver Code
n = 2
m = 2
arr = [ 1, 2, 3, 4 ]
minMaxValues(arr, n, m)
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# program to find the maximum
// and minimum values of an Algebraic
// expression of given form
using System;
using System.Collections.Generic;
class GFG {
static double INF = 1e9;
static int MAX = 50;
static void minMaxValues(int []arr, int n, int m)
{
// Finding sum of array elements
int sum = 0;
for (int i = 0; i < (n + m); i++)
{
sum += arr[i];
// shifting the integers by 50
// so that they become positive
arr[i] += 50;
}
// dp[i][j] represents true if sum
// j can be reachable by choosing
// i numbers
bool[,] dp = new bool[MAX+1, MAX * MAX + 1];
dp[0,0] = true;
// if dp[i][j] is true, that means
// it is possible to select i numbers
// from (n + m) numbers to sum upto j
for (int i = 0; i < (n + m); i++) {
// k can be at max n because the
// left expression has n numbers
for (int k = Math.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]] = true;
}
}
}
double max_value = -1 * INF, min_value = INF;
for (int i = 0; i < MAX * MAX + 1; i++)
{
// checking if a particular sum
// can be reachable by choosing
// n numbers
if (dp[n,i]) {
// getting the actual sum as
// we shifted the numbers by
/// 50 to avoid negative indexing
// in array
int temp = i - 50 * n;
max_value = Math.Max(max_value, temp *
(sum - temp));
min_value = Math.Min(min_value, temp *
(sum - temp));
}
}
Console.WriteLine("Maximum Value: " + max_value
+ "\n" + "Minimum Value: " + min_value + "\n");
}
// Driver Code
public static void Main()
{
int n = 2, m = 2;
int []arr = { 1, 2, 3, 4 };
minMaxValues(arr, n, m);
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to find the
// maximum and minimum values
// of an Algebraic expression
// of given form
function minMaxValues($arr, $n, $m)
{
// Finding sum of
// array elements
$sum = 0;
$INF = 1000000000;
$MAX = 50;
for ($i = 0; $i < ($n + $m); $i++)
{
$sum += $arr[$i];
// shifting the integers by 50
// so that they become positive
$arr[$i] += 50;
}
// dp[i][j] represents true
// if sum j can be reachable
// by choosing i numbers
$dp = array();
// new bool[MAX+1, MAX * MAX + 1];
for($i = 0; $i < $MAX + 1; $i++)
{
for($j = 0; $j < $MAX * $MAX + 1; $j++)
$dp[$i][$j] = 0;
}
$dp[0][0] = 1;
// if dp[i][j] is true, that
// means it is possible to
// select i numbers from (n + m)
// numbers to sum upto j
for ($i = 0; $i < ($n + $m); $i++)
{
// k can be at max n because the
// left expression has n numbers
for ($k = min($n, $i + 1);
$k >= 1; $k--)
{
for ($j = 0; $j < $MAX *
$MAX + 1; $j++)
{
if ($dp[$k - 1][$j])
$dp[$k][$j + $arr[$i]] = 1;
}
}
}
$max_value = -1 * $INF;
$min_value = $INF;
for ($i = 0; $i < $MAX * $MAX + 1; $i++)
{
// checking if a particular
// sum can be reachable by
// choosing n numbers
if ($dp[$n][$i])
{
// getting the actual sum
// as we shifted the numbers
// by 50 to avoid negative
// indexing in array
$temp = $i - 50 * $n;
$max_value = max($max_value, $temp *
($sum - $temp));
$min_value = min($min_value, $temp *
($sum - $temp));
}
}
echo ("Maximum Value: ". $max_value. "\n".
"Minimum Value: ". $min_value. "\n");
}
// Driver Code
$n = 2;
$m = 2;
$arr = [ 1, 2, 3, 4 ];
minMaxValues($arr, $n, $m);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to find the maximum
// and minimum values of an Algebraic
// expression of given form
var INF = 1000000000
var MAX = 50
function minMaxValues(arr, n, m)
{
// Finding sum of array elements
var sum = 0;
for (var i = 0; i < (n + m); i++) {
sum += arr[i];
// shifting the integers by 50
// so that they become positive
arr[i] += 50;
}
// dp[i][j] represents true if sum
// j can be reachable by choosing
// i numbers
var dp = Array.from(Array(MAX+1), ()=> Array(MAX*MAX + 1).fill(0));
dp[0][0] = 1;
// if dp[i][j] is true, that means
// it is possible to select i numbers
// from (n + m) numbers to sum upto j
for (var i = 0; i < (n + m); i++) {
// k can be at max n because the
// left expression has n numbers
for (var k = Math.min(n, i + 1); k >= 1; k--) {
for (var j = 0; j < MAX * MAX + 1; j++) {
if (dp[k - 1][j])
dp[k][j + arr[i]] = 1;
}
}
}
var max_value = -INF, min_value = INF;
for (var i = 0; i < MAX * MAX + 1; i++) {
// checking if a particular sum
// can be reachable by choosing
// n numbers
if (dp[n][i]) {
// getting the actual sum as
// we shifted the numbers by
/// 50 to avoid negative indexing
// in array
var temp = i - 50 * n;
max_value = Math.max(max_value, temp * (sum - temp));
min_value = Math.min(min_value, temp * (sum - temp));
}
}
document.write( "Maximum Value: " + max_value
+ "<br>"
+ "Minimum Value: "
+ min_value );
}
// Driver Code
var n = 2, m = 2;
var arr =[1, 2, 3, 4];
minMaxValues(arr, n, m);
</script>
Producción :
Maximum Value: 25 Minimum Value: 21
Este enfoque tendrá una complejidad de tiempo de ejecución de O(MAX * MAX * (n+m) 2 ).
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA