Valor máximo de (arr[i] * arr[j]) + (arr[j] – arr[i])) posible para cualquier par en una array

Dada una array arr[] que consta de N enteros, la tarea es encontrar el valor máximo posible de la expresión (arr[i] * arr[j]) + (arr[j] – arr[i])) para cualquier par (i, j) , tales que i ≠ j y 0 ≤ (i, j) < N .

Ejemplos:

Entrada: arr[] = {-2, -8, 0, 1, 2, 3, 4}
Salida: 22
Explicación:
Para el par (-8, -2) el valor de la expresión (arr[i] * arr [j]) + (arr[j] – arr[i])) = ((-2)*(-8) + (-2 – (-8))) = 22, que es el máximo entre todos los pares posibles.

Entrada: arr[] = {-47, 0, 12}
Salida: 47

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles de la array y encontrar el valor de la expresión dada (arr[i] * arr[j]) + (arr[j] – arr[i] )) para cada par e imprimir el valor máximo obtenido para cualquier par.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: también se puede optimizar el enfoque anterior, que se basa en la observación de que el valor máximo de la expresión se obtendrá seleccionando los pares de máximo y segundo máximo o mínimo y segundo mínimo de la array. Siga los pasos a continuación para resolver el problema:

Inicialice una variable, digamos ans , para almacenar el valor máximo resultante.
Ordene la array en orden ascendente .
Encuentre los elementos máximo y segundo máximo de la array , digamos X e Y respectivamente, y actualice el valor de ans al máximo de ans y el valor de la expresión con valores X e Y.
Encuentre los elementos mínimo y segundo mínimo de la array , digamos X e Y respectivamente, y actualice el valor de ans al máximo de ans y el valor de la expresión con valores X e Y.
Después de completar los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the value of
// the expression a * b + (b - a)
int calc(int a, int b)
{
    return a * b + (b - a);
}
 
// Function to find the maximum value
// of the expression a * b + (b - a)
// possible for any pair (a, b)
int findMaximum(vector<int> arr, int N)
{
    // Sort the vector in ascending order
    sort(arr.begin(), arr.end());
 
    // Stores the maximum value
    int ans = -1e9;
 
    // Update ans by choosing the pair
    // of the minimum and 2nd minimum
    ans = max(ans, calc(arr[0], arr[1]));
 
    // Update ans by choosing the pair
    // of maximum and 2nd maximum
    ans = max(ans, calc(arr[N - 2],
                        arr[N - 1]));
 
    // Return the value of ans
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 0, -47, 12 };
    int N = (int)arr.size();
    cout << findMaximum(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
     
// Function to find the value of
// the expression a * b + (b - a)
static int calc(int a, int b)
{
    return a * b + (b - a);
}
 
// Function to find the maximum value
// of the expression a * b + (b - a)
// possible for any pair (a, b)
static int findMaximum(int[] arr, int N)
{
     
    // Sort the vector in ascending order
    Arrays.sort(arr);
 
    // Stores the maximum value
    int ans = (int)-1e9;
 
    // Update ans by choosing the pair
    // of the minimum and 2nd minimum
    ans = Math.max(ans, calc(arr[0], arr[1]));
 
    // Update ans by choosing the pair
    // of maximum and 2nd maximum
    ans = Math.max(ans, calc(arr[N - 2],
                             arr[N - 1]));
 
    // Return the value of ans
    return ans;
}   
 
// Driver Code
public static void main(String[] args)
{
     
    // Given inputs
    int[] arr = { 0, -47, 12 };
    int N = arr.length;
     
    System.out.println(findMaximum(arr, N));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
 
# Function to find the value of
# the expression a * b + (b - a)
def calc(a, b):
    return a * b + (b - a)
 
# Function to find the maximum value
# of the expression a * b + (b - a)
# possible for any pair (a, b)
def findMaximum(arr, N):
   
    # Sort the vector in ascending order
    arr = sorted(arr)
 
    # Stores the maximum value
    ans = -10**9
 
    # Update ans by choosing the pair
    # of the minimum and 2nd minimum
    ans = max(ans, calc(arr[0], arr[1]))
 
    # Update ans by choosing the pair
    # of maximum and 2nd maximum
    ans = max(ans, calc(arr[N - 2],arr[N - 1]))
 
    # Return the value of ans
    return ans
 
# Driver Code
if __name__ == '__main__':
    arr = [0, -47, 12]
    N = len(arr)
    print (findMaximum(arr, N))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
   
    // Function to find the value of
    // the expression a * b + (b - a)
    static int calc(int a, int b)
    {
        return a * b + (b - a);
    }
 
    // Function to find the maximum value
    // of the expression a * b + (b - a)
    // possible for any pair (a, b)
    static int findMaximum(List<int> arr, int N)
    {
       
        // Sort the vector in ascending order
        arr.Sort();
 
        // Stores the maximum value
        int ans = -1000000000;
 
        // Update ans by choosing the pair
        // of the minimum and 2nd minimum
        ans = Math.Max(ans, calc(arr[0], arr[1]));
 
        // Update ans by choosing the pair
        // of maximum and 2nd maximum
        ans = Math.Max(ans, calc(arr[N - 2], arr[N - 1]));
 
        // Return the value of ans
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        List<int> arr = new List<int>{ 0, -47, 12 };
        int N = (int)arr.Count;
        Console.Write(findMaximum(arr, N));
    }
}
 
// This code is contributed by ukasp..

Javascript

<script>
        // Javascript program for the above approach
 
        // Function to find the value of
        // the expression a * b + (b - a)
        function calc(a, b) {
            return (a * b) + (b - a);
        }
 
        // Function to find the maximum value
        // of the expression a * b + (b - a)
        // possible for any pair (a, b)
        function findMaximum(arr, N) {
 
            // Sohe vector in ascending order
            arr.sort(function(a, b){return a - b})
 
            // Stores the maximum value
            let ans = Number.MIN_VALUE;
 
            // Update ans by choosing the pair
            // of the minimum and 2nd minimum
            ans = Math.max(ans, calc(arr[0], arr[1]));
 
            // Update ans by choosing the pair
            // of maximum and 2nd maximum
            ans = Math.max(ans, calc(arr[N - 2],
                arr[N - 1]));
 
            // Return the value of ans
            return ans;
        }
 
        // Driver Code
 
        // Given inputs
        let arr = [-47, 0, 12]
 
        let N = arr.length;
 
        document.write(findMaximum(arr, N));
 
        // This code is contributed by Hritik
    </script>

Producción:

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por yoji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta