Programa de Python para la diferencia máxima entre grupos de tamaño dos

Dada una array de un número par de elementos, forme grupos de 2 utilizando estos elementos de la array de modo que la diferencia entre el grupo con la suma más alta y el que tenga la suma más baja sea máxima.
Nota: Un elemento puede ser parte de un solo grupo y tiene que ser parte de al menos 1 grupo. 
Ejemplos: 
 

Input : arr[] = {1, 4, 9, 6}
Output : 10
Groups formed will be (1, 4) and (6, 9), 
the difference between highest sum group
(6, 9) i.e 15 and lowest sum group (1, 4)
i.e 5 is 10.


Input : arr[] = {6, 7, 1, 11}
Output : 11
Groups formed will be (1, 6) and (7, 11), 
the difference between highest sum group
(7, 11) i.e 18 and lowest sum group (1, 6)
i.e 7 is 11.

Enfoque simple: podemos resolver este problema haciendo todas las combinaciones posibles y verificando cada conjunto de diferencias de combinación entre el grupo con la suma más alta y con la suma más baja. Se formarían un total de n*(n-1)/2 de tales grupos (nC2). 
Complejidad de tiempo: O (n ^ 3), porque se necesitarán O (n ^ 2) para generar grupos y verificar contra cada grupo. Se necesitarán n iteraciones, por lo que en general toma O (n ^ 3) tiempo.
Enfoque eficiente: podemos utilizar el enfoque codicioso. Ordene toda la array y nuestro resultado es la suma de los dos últimos elementos menos la suma de los dos primeros elementos.
 

# Python 3 program to find minimum difference
# between groups of highest and lowest
def CalculateMax(arr, n):
 
    # Sorting the whole array.
    arr.sort()
    min_sum = arr[0] + arr[1]
    max_sum = arr[n - 1] + arr[n - 2]
    return abs(max_sum - min_sum)
 
# Driver code
arr = [6, 7, 1, 11]
n = len(arr)
print(CalculateMax(arr, n))
 
# This code is contributed
# by Shrikant13

11

Complejidad de tiempo: O (n * log n)
Optimización adicional: 
en lugar de ordenar, podemos encontrar un máximo de dos y un mínimo de dos en tiempo lineal y reducir la complejidad de tiempo a O(n). 
 

# Python Program for Maximum
# difference between groups
# of size two
 
# import the module
import sys
 
def CalculateMax(arr,n):
    first_min=sys.maxsize
    second_min=sys.maxsize
     
    for i in range(n):
        # If current element is smaller than first_min
        # then update both first_min and second_min
        if(arr[i]<first_min):
            second_min=first_min
            first_min = arr[i]
         
        # If arr[i] is in between first and second
        # then update second
        elif(arr[i]<second_min and arr[i]!=first_min):
            second_min=arr[i]
             
    first_max=-1*sys.maxsize
    second_max=-1*sys.maxsize
     
    for i in range(n):
        # If current element is greater than first_max
        # then update both first and second
        if(arr[i]>first_max):
            second_max=first_max
            first_max = arr[i]
         
        # If arr[i] is in between first_max and
        # second_max then update second
        elif(arr[i]>second_max and arr[i]!=first_max):
            second_max=arr[i]
         
    return abs(first_max+second_max-first_min-second_min)
 
 
# Driver code
arr = [ 6, 7, 1, 11 ];
n = len(arr)
print(CalculateMax(arr, n))
 
# This code is contributed by Pushpesh Raj

11

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

Consulte el artículo completo sobre la diferencia máxima entre grupos de tamaño dos para obtener más detalles.