Programa C++ para 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.
 

// CPP program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
ll CalculateMax(ll arr[], int n)
{
    // Sorting the whole array.
    sort(arr, arr + n);
    
    int min_sum = arr[0] + arr[1];
    int max_sum = arr[n-1] + arr[n-2];
 
    return abs(max_sum - min_sum);
}
 
// Driver code
int main()
{
    ll arr[] = { 6, 7, 1, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << CalculateMax(arr, n) << endl;
    return 0;
}

Producción:  

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). 

 A continuación se muestra el código para el enfoque anterior.

// C++ program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
using namespace std;
 
int CalculateMax(int arr[], int n)
{
     
    int first_min = *min_element(arr, arr + n);;
    int second_min = INT_MAX;
    for(int i = 0; i < n ; i ++)
    {
        // If arr[i] is not equal to first min
        if (arr[i] != first_min)
            second_min = min(arr[i],second_min);
    }
     
    int first_max = *max_element(arr, arr + n);
    int second_max = INT_MIN;
    for (int i = 0; i < n ; i ++)
    {
        // If arr[i] is not equal to first max
        if (arr[i] != first_max)
            second_max = max(arr[i],second_max);
    }
     
    return abs(first_max+second_max-first_min-second_min);
     
}
 
// Driver code
int main()
{
    int arr[] = { 6, 7, 1, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << CalculateMax(arr, n) << endl;
    return 0;
}
 
// This code is contributed by Aman Kumar

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.