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.
C++
// 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;
}
Java
// Java program to find minimum difference
// between groups of highest and lowest
// sums.
import java.util.Arrays;
import java.io.*;
class GFG {
static int CalculateMax(int arr[], int n)
{
// Sorting the whole array.
Arrays.sort(arr);
int min_sum = arr[0] + arr[1];
int max_sum = arr[n-1] + arr[n-2];
return (Math.abs(max_sum - min_sum));
}
// Driver code
public static void main (String[] args) {
int arr[] = { 6, 7, 1, 11 };
int n = arr.length;
System.out.println (CalculateMax(arr, n));
}
}
Python3
# 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
C#
// C# program to find minimum difference
// between groups of highest and lowest
// sums.
using System;
public class GFG{
static int CalculateMax(int []arr, int n)
{
// Sorting the whole array.
Array.Sort(arr);
int min_sum = arr[0] + arr[1];
int max_sum = arr[n-1] + arr[n-2];
return (Math.Abs(max_sum - min_sum));
}
// Driver code
static public void Main (){
int []arr = { 6, 7, 1, 11 };
int n = arr.Length;
Console.WriteLine(CalculateMax(arr, n));
}
//This code is contributed by Sachin.
}
PHP
<?php
// PHP program to find minimum
// difference between groups of
// highest and lowest sums.
function CalculateMax($arr, $n)
{
// Sorting the whole array.
sort($arr);
$min_sum = $arr[0] +
$arr[1];
$max_sum = $arr[$n - 1] +
$arr[$n - 2];
return abs($max_sum -
$min_sum);
}
// Driver code
$arr = array (6, 7, 1, 11 );
$n = sizeof($arr);
echo CalculateMax($arr, $n), "\n" ;
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to
// find minimum difference
// between groups of highest and lowest
// sums.
function CalculateMax(arr, n)
{
// Sorting the whole array.
arr.sort(function(a, b){return a - b});
let min_sum = arr[0] + arr[1];
let max_sum = arr[n-1] + arr[n-2];
return (Math.abs(max_sum - min_sum));
}
let arr = [ 6, 7, 1, 11 ];
let n = arr.length;
document.write(CalculateMax(arr, n));
</script>
Producción
11
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).
C++
// CPP 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 = INT_MAX;
int second_min = INT_MAX;
for(int i = 0; i < n ; i ++)
{
/* If current element is smaller than first
then update both first and second */
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 */
else if (arr[i] < second_min && arr[i] != first_min)
second_min = arr[i];
}
int first_max = INT_MIN;
int second_max = INT_MIN;
for (int i = 0; i < n ; i ++)
{
/* If current element is smaller than first
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 and second
then update second */
else if (arr[i] > second_max && arr[i] != first_max)
second_max = arr[i];
}
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 Pushpesh Raj
Java
// Java program to find minimum difference
// between groups of highest and lowest
// sums.
import java.util.Arrays;
import java.io.*;
class GFG {
static int CalculateMax(int arr[], int n)
{
int first_min = Integer.MAX_VALUE;
int second_min = Integer.MAX_VALUE;
for(int i = 0; i < n ; i ++)
{
/* If current element is smaller than first
then update both first and second */
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 */
else if (arr[i] < second_min && arr[i] != first_min)
second_min = arr[i];
}
int first_max = Integer.MIN_VALUE;
int second_max = Integer.MIN_VALUE;
for (int i = 0; i < n ; i ++)
{
/* If current element is smaller than first
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 and second
then update second */
else if (arr[i] > second_max && arr[i] != first_max)
second_max = arr[i];
}
return Math.abs(first_max+second_max-first_min-second_min);
}
// Driver code
public static void main (String[] args) {
int arr[] = { 6, 7, 1, 11 };
int n = arr.length;
System.out.println (CalculateMax(arr, n));
}
}
Python3
# Python 3 program to find minimum difference # between groups of highest and lowest def CalculateMax(arr, n): # maxint constant first_min = 99999 second_min = 99999 for i in range(n): 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 & arr[i] != first_min: second_min = arr[i] # maxint constant first_max = -99999 second_max = -99999 for i in range(n): if arr[i] > first_max: second_max = first_max first_max = arr[i] # If arr[i] is in between first and second # then update second elif arr[i] > second_max & 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 Aarti_Rathi
C#
// C# program to find minimum difference
// between groups of highest and lowest
// sums.
using System;
public class GFG{
static int CalculateMax(int []arr, int n)
{
int first_min = int.MaxValue;
int second_min = int.MaxValue;
for(int i = 0; i < n ; i ++)
{
/* If current element is smaller than first
then update both first and second */
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 */
else if (arr[i] < second_min && arr[i] != first_min)
second_min = arr[i];
}
int first_max = int.MinValue;
int second_max = int.MinValue;
for (int i = 0; i < n ; i ++)
{
/* If current element is smaller than first
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 and second
then update second */
else if (arr[i] > second_max && arr[i] != first_max)
second_max = arr[i];
}
return Math.Abs(first_max+second_max-first_min-second_min);
}
// Driver code
static public void Main (){
int []arr = { 6, 7, 1, 11 };
int n = arr.Length;
Console.WriteLine(CalculateMax(arr, n));
}
}
Javascript
<script>
// Javascript program to
// find minimum difference
// between groups of highest and lowest
// sums.
function CalculateMax(arr, n)
{
let first_min = Number.MAX_VALUE;
let second_min = Number.MAX_VALUE;
for(let i = 0; i < n ; i ++)
{
/* If current element is smaller than first
then update both first and second */
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 */
else if (arr[i] < second_min && arr[i] != first_min)
second_min = arr[i];
}
let first_max = Number.MIN_VALUE;
let second_max = Number.MIN_VALUE;
for (let i = 0; i < n ; i ++)
{
/* If current element is smaller than first
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 and second
then update second */
else if (arr[i] > second_max && arr[i] != first_max)
second_max = arr[i];
}
return Math.abs(first_max+second_max-first_min-second_min);
}
let arr = [ 6, 7, 1, 11 ];
let n = arr.length;
document.write(CalculateMax(arr, n));
</script>
Producción
11
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)