Encuentre la suma de la diferencia máxima posible de todos los subconjuntos de una array dada.

Nos dan una array arr[] de n enteros no negativos (se permiten elementos repetidos), averigüe la suma de la diferencia máxima posible de todos los subconjuntos de la array dada. 
Supongamos que max(s) representa el valor máximo en cualquier subconjunto ‘s’ mientras que min(s) representa el valor mínimo en el conjunto ‘s’. Necesitamos encontrar la suma de max(s)-min(s) para todos los subconjuntos posibles.

Ejemplos: 

Input : arr[] = {1, 2, 3}
Output : result = 6

Explanation : 
All possible subset and for each subset s,
max(s)-min(s) are as :
SUBSET    |  max(s) | min(s) | max(s)-min(s)
{1, 2}    |  2      |  1     |   1
{1, 3}    |  3      |  1     |   2
{2, 3}    |  3      |  2     |   1
{1, 2, 3} |  3      |  1     |   2
Total Difference sum = 6
Note : max(s) - min(s) for all subset with 
single element must be zero.

Input : arr[] = {1, 2, 2}
Output : result = 3

Explanation : 
All possible subset and for each subset s,
max(s)-min(s) are as :
  SUBSET  |  max(s) | min(s)| max(s)-min(s)
  {1, 2}  |  2      |  1    |   1
  {1, 2}  |  2      |  1    |   1
  {2, 2}  |  2      |  2    |   0
{1, 2, 2} |  2      |  1    |   1
Total Difference sum = 3

Enfoque básico: 

Calcule la suma del elemento máximo de cada subconjunto y la suma del elemento mínimo de cada subconjunto por separado, y luego reste la suma mínima del máximo para obtener la respuesta. La suma del elemento máximo/mínimo de cada subconjunto se puede calcular fácilmente iterando a través de los elementos de cada subconjunto. Pero como tenemos que iterar a través de todos los subconjuntos, la complejidad del tiempo para este enfoque es exponencial O(n2^n).

Enfoque eficiente: 

Como tenemos que calcular la suma del elemento máximo de cada subconjunto y la suma del elemento mínimo de cada subconjunto por separado, esta es una forma eficiente de realizar este cálculo. 

Suma de elementos mínimos de todos los subconjuntos: 

Digamos que los elementos de arr[] en orden no decreciente son {a1,a2,…, an}. Ahora, podemos dividir los subconjuntos de arr[] en las siguientes categorías: 

• Subconjuntos que contienen el elemento a1: estos subconjuntos se pueden obtener tomando cualquier subconjunto de {a2,a3,…, an} y luego añadiéndole a1. El número de dichos subconjuntos será 2 ^n-1 , y todos tienen a1 como elemento mínimo.
• Subconjuntos que no contienen el elemento a1, pero contienen a2: estos subconjuntos se pueden obtener tomando cualquier subconjunto de {a3, a4,…,an} y luego agregando a2 en él. El número de dichos subconjuntos será 2 ^n-2 y todos tienen a2 como elemento mínimo.
• …..
• Subconjuntos que no contienen los elementos a1, a2,…, ai-1 pero que contienen ai: estos subconjuntos se pueden obtener tomando cualquier subconjunto de {ai+1,ai+2,…, an} y luego añadiéndole ai. El número de tales subconjuntos será 2 ^n-i , y todos ellos tienen ai como su elemento mínimo.

se puede ver que la iteración anterior es completa, es decir, considera cada subconjunto exactamente una vez. Por lo tanto, la suma del elemento mínimo de todos los subconjuntos será:
min_sum = a1*2 ^n-1 + a2*2 ^n-2 + … + an*2 ⁰ 
Esta suma se puede calcular fácilmente en tiempo lineal con la ayuda de Horner método …
De manera similar, podemos calcular la suma del elemento máximo de todos los subconjuntos de arr[]. La única diferencia es que necesitamos iterar los elementos de arr[] en orden no creciente. 

Nota: Es posible que tengamos una respuesta larga, por lo que debemos calcular la respuesta con mod 10^9 +7.

// CPP for finding max min difference
// from all subset of given set
#include <bits/stdc++.h>
using namespace std;
 
const long long int MOD = 1000000007;
 
// function for sum of max min difference
int maxMin (int arr[], int n)
{
    // sort all numbers
    sort(arr, arr + n);
     
    // iterate over array and with help of
    // horner's rule calc max_sum and min_sum
    long long int min_sum = 0, max_sum = 0;
    for (int i = 0; i < n; i++)
    {
        max_sum = 2 * max_sum + arr[n-1-i];
        max_sum %= MOD;
        min_sum = 2 * min_sum + arr[i];
        min_sum %= MOD;
    }
 
    return (max_sum - min_sum + MOD) % MOD;
}
 
// Driver Code
int main()
{
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxMin(arr,n);
    return 0;
}

// JAVA Code for Find the sum of maximum
// difference possible from all subset
// of a given array.
import java.util.*;
 
class GFG {
     
    public static int MOD = 1000000007;
     
    // function for sum of max min difference
    public static long maxMin (int arr[], int n)
    {
        // sort all numbers
        Arrays.sort(arr);
         
        // iterate over array and with help of
        // horner's rule calc max_sum and min_sum
        long min_sum = 0, max_sum = 0;
        for (int i = 0; i < n; i++)
        {
            max_sum = 2 * max_sum + arr[n - 1 - i];
            max_sum %= MOD;
            min_sum = 2 * min_sum + arr[i];
            min_sum %= MOD;
        }
     
        return (max_sum - min_sum + MOD)%MOD;
    }
     
    // Driver Code
    public static void main(String[] args)
    {
            int arr[] = {1, 2, 3, 4};
            int n = arr.length;
            System.out.println(maxMin(arr, n));
    }
}
 
// This code is contributed by Arnav Kr. Mandal.

# python for finding max min difference
#from all subset of given set
 
MOD = 1000000007;
 
# function for sum of max min difference
def maxMin (arr,n):
     
    # sort all numbers
    arr.sort()
     
    # iterate over array and with help of
    # horner's rule calc max_sum and min_sum
    min_sum = 0
    max_sum = 0
    for i in range(0,n):
         
        max_sum = 2 * max_sum + arr[n-1-i];
        max_sum %= MOD;
        min_sum = 2 * min_sum + arr[i];
        min_sum %= MOD;
     
    return (max_sum - min_sum + MOD) % MOD;
 
# Driver Code
arr = [1, 2, 3, 4]
n = len(arr)
print( maxMin(arr, n))
 
# This code is contributed by Sam007.

// C# Code to Find the sum of maximum
// difference possible from all subset
// of a given array.
using System;
 
class GFG {
     
    public static int MOD = 1000000007;
     
    // function for sum of max min difference
    public static long maxMin (int []arr, int n)
    {
        // sort all numbers
        Array.Sort(arr);
         
        // iterate over array and with help of
        // horner's rule calc max_sum and min_sum
        long min_sum = 0, max_sum = 0;
        for (int i = 0; i < n; i++)
        {
            max_sum = 2 * max_sum + arr[n - 1 - i];
            max_sum %= MOD;
            min_sum = 2 * min_sum + arr[i];
            min_sum %= MOD;
        }
     
        return (max_sum - min_sum + MOD) % MOD;
    }
     
    // Driver Code
    public static void Main()
    {
            int []arr = {1, 2, 3, 4};
            int n = arr.Length;
            Console.Write(maxMin(arr, n));   
    }
}
 
// This code is contributed by nitin mittal

<?php
// PHP for finding max min difference
// from all subset of given set
$MOD = 1000000007;
 
// function for sum of
// max min difference
function maxMin ($arr, $n)
{
    global $MOD;
     
    // sort all numbers
    sort($arr);
     
    // iterate over array
    // and with help of
    // horner's rule calc
    // max_sum and min_sum
    $min_sum = 0; $max_sum = 0;
     
    for ($i = 0; $i < $n;$i++)
    {
        $max_sum = 2 * $max_sum +
                       $arr[$n - 1 - $i];
        $max_sum %= $MOD;
        $min_sum = 2 * $min_sum + $arr[$i];
        $min_sum %= $MOD;
    }
 
    return ($max_sum - $min_sum + $MOD) % $MOD;
}
 
// Driver Code
$arr = array(1, 2, 3, 4);
$n = count($arr);
echo maxMin($arr, $n);
 
// This code is contributed by vt_m.
?>

<script>
 
// Javascript for finding max min difference
// from all subset of given set
 
var MOD = 1000000007;
 
// function for sum of max min difference
function maxMin (arr, n)
{
    // sort all numbers
    arr.sort((a,b)=> a-b);
     
    // iterate over array and with help of
    // horner's rule calc max_sum and min_sum
    var min_sum = 0, max_sum = 0;
    for (var i = 0; i < n; i++)
    {
        max_sum = 2 * max_sum + arr[n-1-i];
        max_sum %= MOD;
        min_sum = 2 * min_sum + arr[i];
        min_sum %= MOD;
    }
 
    return (max_sum - min_sum + MOD) % MOD;
}
 
// Driver Code
var arr = [1, 2, 3, 4];
var n = arr.length;
document.write( maxMin(arr,n));
 
</script>

23

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.