Encuentre el valor máximo del último elemento después de reducir la array con operaciones dadas

Posted on by Rudeus Greyrat

Dada una array arr[] de N elementos, debe realizar la siguiente operación en la array dada hasta que la array se reduzca a un solo elemento, 
 

  1. Elige dos índices i y j tales que i != j .
  2. Reemplace arr[i] con arr[i] – arr[j] y elimine arr[j] de la array.

La tarea es maximizar e imprimir el valor del último elemento restante de la array.
Ejemplos: 
 

Entrada: arr[] = {20, 3, -15, 7} 
Salida: 45 
Paso 1: Podemos eliminar 7 y reemplazar -15 con -22. 
paso 2: Podemos eliminar 3 y reemplazar -22 con -25. 
paso 3: podemos eliminar -25 y reemplazar 20 con 45. 
Entonces 45 es el valor máximo que podemos obtener.
Entrada: arr[] = {5, 4, 6, 2} 
Salida: 13 
 

Enfoque: Para maximizar el valor del último elemento restante, hay tres casos: 
 

  1. La array tiene números negativos y positivos: primero restaremos todos los números positivos (excepto uno) de los números negativos. Después de esto, solo nos quedará un solo número positivo y un solo número negativo. Ahora, restaremos ese número negativo del positivo, lo que finalmente dará como resultado un número positivo. Entonces, en este caso, el resultado es la suma de los valores absolutos de los elementos de la array.
  2. La array contiene solo números positivos: primero encontramos el número más pequeño y luego le restamos todos los números positivos excepto un número positivo. Después de esto, obtenemos solo un número positivo y un número negativo, ahora restaremos el número negativo de ese número positivo, lo que finalmente dará como resultado un número positivo. Aquí podemos observar que el 
    número más pequeño se ha desvanecido y también el valor básicamente se elimina del siguiente elemento mayor, que es diferente del caso 1. Entonces, en este caso, el resultado es la suma de los valores absolutos de los elementos de la array: 2 * elemento mínimo .
  3. La array contiene solo números negativos: primero encontramos el número más grande y luego restamos todos los números negativos excepto un número negativo. Después de esto, obtenemos solo un número negativo y un número positivo, ahora restaremos el número negativo del positivo, lo que dará como resultado un número positivo. Aquí podemos observar que el número más grande se ha desvanecido y también el valor básicamente se elimina del siguiente elemento mayor que es diferente del caso 1. Entonces, en este caso, el resultado es la suma de los valores absolutos de los elementos de la array: 2 * absoluto de elemento más grande. Aquí tomamos el mayor como absoluto del mayor es el menor en el caso de un número negativo.

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximized value
int find_maximum_value(int a[], int n)
{
    int sum = 0;
    int minimum = INT_MAX;
    int pos = 0, neg = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Overall minimum absolute value
        // of some element from the array
        minimum = min(minimum, abs(a[i]));
 
        // Add all absolute values
        sum += abs(a[i]);
 
        // Count positive and negative elements
        if (a[i] >= 0)
            pos += 1;
        else
            neg += 1;
    }
 
    // Both positive and negative
    // values are present
    if (pos > 0 && neg > 0)
        return sum;
 
    // Only positive or negative
    // values are present
    return (sum - 2 * minimum);
}
 
// Driver code
int main()
{
    int a[] = { 5, 4, 6, 2 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << find_maximum_value(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
    // Function to return the maximized value
    static int find_maximum_value(int a[], int n)
    {
        int sum = 0;
        int minimum = Integer.MAX_VALUE;
        int pos = 0, neg = 0;
     
        for (int i = 0; i < n; i++)
        {
     
            // Overall minimum absolute value
            // of some element from the array
            minimum = Math.min(minimum, Math.abs(a[i]));
     
            // Add all absolute values
            sum += Math.abs(a[i]);
     
            // Count positive and negative elements
            if (a[i] >= 0)
                pos += 1;
            else
                neg += 1;
        }
     
        // Both positive and negative
        // values are present
        if (pos > 0 && neg > 0)
            return sum;
     
        // Only positive or negative
        // values are present
        return (sum - 2 * minimum);
    }
     
    // Driver code
    public static void main (String[] args)
    {
         
        int []a = { 5, 4, 6, 2 };
        int n = a.length;
     
        System.out.println(find_maximum_value(a, n));
    }
}
 
// This code is contributed by ajit

Python

# Python3 implementation of the approach
 
# Function to return the maximized value
def find_maximum_value(a, n):
     
    sum = 0
    minimum = 10**9
    pos = 0
    neg = 0
 
    for i in range(n):
 
        # Overall minimum absolute value
        # of some element from the array
        minimum = min(minimum, abs(a[i]))
 
        # Add all absolute values
        sum += abs(a[i])
 
        # Count positive and negative elements
        if (a[i] >= 0):
            pos += 1
        else:
            neg += 1
 
    # Both positive and negative
    # values are present
    if (pos > 0 and neg > 0):
        return sum
 
    # Only positive or negative
    # values are present
    return (sum - 2 * minimum)
 
# Driver code
 
a= [5, 4, 6, 2]
n = len(a)
 
print(find_maximum_value(a, n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the maximized value
    static int find_maximum_value(int []a, int n)
    {
        int sum = 0;
        int minimum = int.MaxValue;
        int pos = 0, neg = 0;
     
        for (int i = 0; i < n; i++)
        {
     
            // Overall minimum absolute value
            // of some element from the array
            minimum = Math.Min(minimum, Math.Abs(a[i]));
     
            // Add all absolute values
            sum += Math.Abs(a[i]);
     
            // Count positive and negative elements
            if (a[i] >= 0)
                pos += 1;
            else
                neg += 1;
        }
     
        // Both positive and negative
        // values are present
        if (pos > 0 && neg > 0)
            return sum;
     
        // Only positive or negative
        // values are present
        return (sum - 2 * minimum);
    }
     
    // Driver code
    static public void Main ()
    {
        int []a = { 5, 4, 6, 2 };
        int n = a.Length;
     
        Console.WriteLine(find_maximum_value(a, n));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
// javascript implementation of the approach
 
    // Function to return the maximized value
    function find_maximum_value(a , n) {
        var sum = 0;
        var minimum = Number.MAX_VALUE;
        var pos = 0, neg = 0;
 
        for (i = 0; i < n; i++) {
 
            // Overall minimum absolute value
            // of some element from the array
            minimum = Math.min(minimum, Math.abs(a[i]));
 
            // Add all absolute values
            sum += Math.abs(a[i]);
 
            // Count positive and negative elements
            if (a[i] >= 0)
                pos += 1;
            else
                neg += 1;
        }
 
        // Both positive and negative
        // values are present
        if (pos > 0 && neg > 0)
            return sum;
 
        // Only positive or negative
        // values are present
        return (sum - 2 * minimum);
    }
 
    // Driver code
        var a = [ 5, 4, 6, 2 ];
        var n = a.length;
 
        document.write(find_maximum_value(a, n));
 
// This code is contributed by todaysgaurav
</script>
Producción: 

13

 

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *