Maximiere bei einem Array und drei Zahlen (x * a[i]) + (y * a[j]) + (z * a[k])
Gegeben sei ein Array aus n ganzen Zahlen und drei ganzen Zahlen x, y und z. maximieren Sie den Wert von (x * a[i]) + (y * a[j]) + (z * a[k]), wobei i ≤ j ≤ k.
Beispiele:
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
Eine einfache Lösung besteht darin, drei verschachtelte Schleifen auszuführen, um alle Tripletts zu durchlaufen. Berechnen Sie für jedes Triplett den erforderlichen Wert und verfolgen Sie das Maximum und geben Sie schließlich dasselbe zurück.
Eine effiziente Lösung besteht darin, Werte vorzuberechnen und sie mit zusätzlichem Speicherplatz zu speichern. Die erste Schlüsselbeobachtung ist i ≤ j ≤ k, also ist x*a[i] immer das linke Maximum und z*a[k] immer das rechte Maximum. Erstellen Sie ein linkes Array, in dem wir die linken Maxima für jedes Element speichern. Erstellen Sie ein richtiges Array, in dem wir die richtigen Maxima für jedes Element speichern. Berechnen Sie dann für jedes Element den maximal möglichen Wert der Funktion. Für jeden Index ind ist das Maximum an dieser Position immer (links[ind] + j * a[ind] + rechts[ind]), finden Sie das Maximum dieses Werts für jedes Element im Array und das wird Ihre Antwort sein .
Unten ist die Implementierung des obigen Ansatzes
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>
Ausgabe :
12
Zeitkomplexität: O(n)
Hilfsraum: O(n)
Dieser Artikel wurde von Raj beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie etwas beitragen möchten, können Sie auch einen Artikel über write.geeksforgeeks.org schreiben oder Ihren Artikel per E-Mail an review-team@geeksforgeeks.org senden. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.
Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .