Dada una array de n enteros y tres enteros x, y y z. maximizar el valor de (x * a[i]) + (y * a[j]) + (z * a[k]) donde i ≤ j ≤ k.
Ejemplos:
Input : arr[] = {-1, -2, -3, -4, -5}
x = 1
y = 2
z = -3
Output: 12
Explanation: The maximized values is
(1 * -1) + (2 * -1) + ( -3 * -5) = 12
Input: arr[] = {1, 2, 3, 4, 5}
x = 1
y = 2
z = 3
Output: 30
(1*5 + 2*5 + 3*5) = 30
Una solución simple es ejecutar tres bucles anidados para iterar a través de todos los tripletes. Para cada triplete, calcule el valor requerido y realice un seguimiento del máximo y finalmente devuelva el mismo.
Una solución eficiente es calcular previamente los valores y almacenarlos utilizando espacio adicional. La primera observación clave es i ≤ j ≤ k, por lo que x*a[i] siempre será el máximo a la izquierda y z*a[k] siempre será el máximo a la derecha. Cree una array izquierda donde almacenemos los máximos izquierdos para cada elemento. Cree una array correcta donde almacenemos los máximos correctos para cada elemento. Luego, para cada elemento, calcule el valor máximo posible de la función. Para cualquier ind de índice, el máximo en esa posición siempre será (left[ind] + j * a[ind] + right[ind]), encuentre el máximo de este valor para cada elemento en la array y esa será su respuesta .
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find the maximum value of
// x*arr[i] + y*arr[j] + z*arr[k]
#include <bits/stdc++.h>
using namespace std;
// function to maximize the condition
int maximizeExpr(int a[], int n, int x, int y,
int z)
{
// Traverse the whole array and compute
// left maximum for every index.
int L[n];
L[0] = x * a[0];
for (int i = 1; i < n; i++)
L[i] = max(L[i - 1], x * a[i]);
// Compute right maximum for every index.
int R[n];
R[n-1] = z * a[n-1];
for (int i = n - 2; i >= 0; i--)
R[i] = max(R[i + 1], z * a[i]);
// Traverse through the whole array to
// maximize the required expression.
int ans = INT_MIN;
for (int i = 0; i < n; i++)
ans = max(ans, L[i] + y * a[i] + R[i]);
return ans;
}
// driver program to test the above function
int main()
{
int a[] = {-1, -2, -3, -4, -5};
int n = sizeof(a)/sizeof(a[0]);
int x = 1, y = 2 , z = -3;
cout << maximizeExpr(a, n, x, y, z) << endl;
return 0;
}
Java
// Java program to find the maximum value
// of x*arr[i] + y*arr[j] + z*arr[k]
import java.io.*;
class GFG {
// function to maximize the condition
static int maximizeExpr(int a[], int n, int x,
int y, int z)
{
// Traverse the whole array and compute
// left maximum for every index.
int L[] = new int[n];
L[0] = x * a[0];
for (int i = 1; i < n; i++)
L[i] = Math.max(L[i - 1], x * a[i]);
// Compute right maximum for every index.
int R[] = new int[n];
R[n - 1] = z * a[n - 1];
for (int i = n - 2; i >= 0; i--)
R[i] = Math.max(R[i + 1], z * a[i]);
// Traverse through the whole array to
// maximize the required expression.
int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
ans = Math.max(ans, L[i] + y * a[i] +
R[i]);
return ans;
}
// driver program to test the above function
public static void main(String[] args)
{
int a[] = {-1, -2, -3, -4, -5};
int n = a.length;
int x = 1, y = 2 , z = -3;
System.out.println(maximizeExpr(a, n, x, y, z));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to find # the maximum value of # x*arr[i] + y*arr[j] + z*arr[k] import sys # function to maximize # the condition def maximizeExpr(a, n, x, y, z): # Traverse the whole array # and compute left maximum # for every index. L = [0] * n L[0] = x * a[0] for i in range(1, n): L[i] = max(L[i - 1], x * a[i]) # Compute right maximum # for every index. R = [0] * n R[n - 1] = z * a[n - 1] for i in range(n - 2, -1, -1): R[i] = max(R[i + 1], z * a[i]) # Traverse through the whole # array to maximize the # required expression. ans = -sys.maxsize for i in range(0, n): ans = max(ans, L[i] + y * a[i] + R[i]) return ans # Driver Code a = [-1, -2, -3, -4, -5] n = len(a) x = 1 y = 2 z = -3 print(maximizeExpr(a, n, x, y, z)) # This code is contributed # by Smitha
C#
// C# program to find the maximum value
// of x*arr[i] + y*arr[j] + z*arr[k]
using System;
class GFG {
// function to maximize the condition
static int maximizeExpr(int []a, int n,
int x, int y, int z)
{
// Traverse the whole array and
// compute left maximum for every
// index.
int []L = new int[n];
L[0] = x * a[0];
for (int i = 1; i < n; i++)
L[i] = Math.Max(L[i - 1], x * a[i]);
// Compute right maximum for
// every index.
int []R = new int[n];
R[n - 1] = z * a[n - 1];
for (int i = n - 2; i >= 0; i--)
R[i] = Math.Max(R[i + 1], z * a[i]);
// Traverse through the whole array to
// maximize the required expression.
int ans = int.MinValue;
for (int i = 0; i < n; i++)
ans = Math.Max(ans, L[i] +
y * a[i] + R[i]);
return ans;
}
// driver program to test the
// above function
public static void Main()
{
int []a = {-1, -2, -3, -4, -5};
int n = a.Length;
int x = 1, y = 2 , z = -3;
Console.WriteLine(
maximizeExpr(a, n, x, y, z));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find the
// maximum value of
// x*arr[i]+ y*arr[j] + z*arr[k]
// function to maximize
// the condition
function maximizeExpr($a, $n,
$x, $y, $z)
{
// Traverse the whole array
// and compute left maximum
// for every index.
$L = array();
$L[0] = $x * $a[0];
for ($i = 1; $i < $n; $i++)
$L[$i] = max($L[$i - 1],
$x * $a[$i]);
// Compute right maximum
// for every index.
$R = array();
$R[$n - 1] = $z * $a[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
$R[$i] = max($R[$i + 1],
$z * $a[$i]);
// Traverse through the whole
// array to maximize the
// required expression.
$ans = PHP_INT_MIN;
for ($i = 0; $i < $n; $i++)
$ans = max($ans, $L[$i] +
$y * $a[$i] + $R[$i]);
return $ans;
}
// Driver Code
$a = array(-1, -2, -3, -4, -5);
$n = count($a);
$x = 1; $y = 2 ; $z = -3;
echo maximizeExpr($a, $n, $x, $y, $z);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript program to find the maximum value
// of x*arr[i] + y*arr[j] + z*arr[k]
// function to maximize the condition
function maximizeExpr(a , n , x , y , z)
{
// Traverse the whole array and compute
// left maximum for every index.
var L = Array(n).fill(0);
L[0] = x * a[0];
for (i = 1; i < n; i++)
L[i] = Math.max(L[i - 1], x * a[i]);
// Compute right maximum for every index.
var R = Array(n).fill(0);
R[n - 1] = z * a[n - 1];
for (i = n - 2; i >= 0; i--)
R[i] = Math.max(R[i + 1], z * a[i]);
// Traverse through the whole array to
// maximize the required expression.
var ans = Number.MIN_VALUE;
for (i = 0; i < n; i++)
ans = Math.max(ans, L[i] + y * a[i] + R[i]);
return ans;
}
// Driver program to test the above function
var a = [ -1, -2, -3, -4, -5 ];
var n = a.length;
var x = 1, y = 2, z = -3;
document.write(maximizeExpr(a, n, x, y, z));
// This code is contributed by Rajput-Ji
</script>
12
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Raj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA