Mínimo de array más grande en operaciones N-1 al reducir cada elemento por mínimo

Dada una array arr[] que contiene N enteros, la tarea es encontrar el máximo de todos los elementos mínimos después de N-1 operaciones de eliminación. En una operación, elimine el elemento más pequeño de la array y réstelo de todos los elementos restantes. 

Ejemplos:

Entrada: arr[] = {-1, -2, 4, 3, 5}
Salida: 4
Explicación: Las siguientes son las operaciones realizadas:
Operación 1: Quitar -2 y restarlo del restante. Ahora la array arr[] se convierte en {1, 6, 5, 7}. elemento mínimo = 1, elemento mínimo máx = 1.
Operación 2: quitar 1 y restarlo del restante. Ahora la array arr[] se convierte en {5, 4, 6}. mínimo elemento =4, max mínimo elemento = 4.
Operación 3: Quitar 4 y restarlo del restante. Ahora arr[] se convierte en {1, 2}. elemento mínimo = 1 elemento mínimo máximo = 4 hasta ahora.
Operación 4: Quitar 1 y restarlo del restante. Ahora arr[] se convierte en {1}. elemento mínimo = 1, elemento mínimo máximo = 4 hasta ahora
Por lo tanto, el elemento mínimo máximo es 4.

Entrada: arr[] = {-3, -1, -6, -7}
Salida: 3

Enfoque ingenuo: elimine el elemento mínimo de la array y realice la resta de los elementos restantes y siga rastreando el máximo de un mínimo de la array en cada operación mientras el tamaño de la array no sea igual a 0.

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

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el enfoque codicioso . Esto se puede derivar matemáticamente ya que el elemento mínimo debe eliminarse cada vez y, por lo tanto, es independiente del orden de los elementos en la array. Por lo tanto, la array debe ordenarse. Siga la observación a continuación, para resolver el problema:

Dado que el elemento Mínimo debe eliminarse en cada operación. Considere que la array después de clasificar en orden creciente es {a1, a2, a3, a4, a5, …}
Inicialmente a1 es el mínimo y después de eliminarlo, la array se convierte en {a2-a1, a3-a1, a4-a1, a5- a1, …}
Ahora a2-a1 es el mínimo y después de eliminarlo, la array se convierte en {a3-a1-(a2-a1), a4-a1-(a2-a1), …} que es igual a {a3-a2 , a4-a2, a5-a2, …}
Ahora a3-a2 es el mínimo y continúa así…
Entonces, res = max(a1, ∑(i=0 to (N-1)) (ai+1 -ai) )

Por lo tanto, el resultado final será la diferencia máxima de dos elementos consecutivos, como se ve en la prueba anterior. Siga los pasos a continuación para resolver el problema:

1. Cree una variable max_value para almacenar la respuesta final e inicialícela con arr[0] .
2. Ordene la array arr[] en orden ascendente.
3. Ejecute un ciclo de i=0 a i<(N-1) , y en cada iteración:
   • Lleve un registro del valor máximo o mínimo (es decir, la diferencia arr[i + 1] – arr[i] ) en cada iteración. Entonces, haga max_value , máximo de max_value y (arr[i+1] – arr[i]) .
4. Devuelve max_value como respuesta final.

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum of minimum value
// of the array in the array
// in each operation
int maxOfAllMins(int arr[], int n)
{
    // If no operations are done
    int max_value = arr[0];
 
    // Sort the array arr in ascending order
    sort(arr, arr + n);
 
    for (int i = 0; i < n - 1; i++) {
        max_value = max(max_value,
                        arr[i + 1] - arr[i]);
    }
 
    return max_value;
}
 
// Driver code
int main()
{
    int arr[] = { -1, -2, 4, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxOfAllMins(arr, N);
    return 0;
}

// Java program for above approach
import java.util.*;
public class GFG {
 
  // Function to find maximum of minimum value
  // of the array in the array
  // in each operation
  static int maxOfAllMins(int[] arr, int n)
  {
 
    // If no operations are done
    int max_value = arr[0];
 
    // Sort the array arr in ascending order
    Arrays.sort(arr);
 
    for (int i = 0; i < n - 1; i++) {
      max_value
        = Math.max(max_value, arr[i + 1] - arr[i]);
    }
 
    return max_value;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int[] arr = { -1, -2, 4, 3, 5 };
    int N = arr.length;
    System.out.println(maxOfAllMins(arr, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 code for the above approach
 
# Function to find maximum of minimum value
# of the array in the array
# in each operation
def maxOfAllMins(arr, n):
 
    # If no operations are done
    max_value = arr[0]
 
    # Sort the array arr in ascending order
    arr.sort()
 
    for i in range(0, n-1):
        max_value = max(max_value,
                        arr[i + 1] - arr[i])
 
    return max_value
 
# Driver code
if __name__ == "__main__":
 
    arr = [-1, -2, 4, 3, 5]
    N = len(arr)
 
    print(maxOfAllMins(arr, N))
 
# This code is contributed by rakeshsahni

// C# code for the above approach
using System;
class GFG {
 
    // Function to find maximum of minimum value
    // of the array in the array
    // in each operation
    static int maxOfAllMins(int[] arr, int n)
    {
        // If no operations are done
        int max_value = arr[0];
 
        // Sort the array arr in ascending order
        Array.Sort(arr);
 
        for (int i = 0; i < n - 1; i++) {
            max_value
                = Math.Max(max_value, arr[i + 1] - arr[i]);
        }
 
        return max_value;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { -1, -2, 4, 3, 5 };
        int N = arr.Length;
        Console.WriteLine(maxOfAllMins(arr, N));
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript code for the above approach
 
 
// Function to find maximum of minimum value
// of the array in the array
// in each operation
function maxOfAllMins(arr, n)
{
    // If no operations are done
    let max_value = arr[0];
 
    // Sort the array arr in ascending order
    arr.sort((a, b) => a - b);
 
    for (let i = 0; i < n - 1; i++) {
        max_value = Math.max(max_value,
                        arr[i + 1] - arr[i]);
    }
 
    return max_value;
}
 
// Driver code
 
let arr = [ -1, -2, 4, 3, 5 ];
let N = arr.length
 
document.write(maxOfAllMins(arr, N));
 
// This code is contributed by gfgking.
</script>

4

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