Partición en dos subconjuntos de longitudes K y (N – k) de modo que la diferencia de sumas sea máxima

Dada una array de enteros no negativos de longitud N y un entero K. Dividir la array dada en dos subconjuntos de longitud K y N – K para que la diferencia entre la suma de ambos subconjuntos sea máxima.

Ejemplos:  

Input : arr[] = {8, 4, 5, 2, 10}
        k = 2
Output : 17
Explanation :
Here, we can make first subset of length k = {4, 2}
and second subset of length N - k = {8, 5, 10}. Then,
the max_difference = (8 + 5 + 10) - (4 + 2) = 17.

Input : arr[] = {1, 1, 1, 1, 1, 1, 1, 1}
        k = 3
Output : 2
Explanation :
Here, subsets would be {1, 1, 1, 1, 1} and {1, 1, 1}.
So, max_difference would be 2

Elige k números con la mayor suma posible. Entonces la solución obviamente es k números más grandes. Para que aquí funcione el algoritmo codicioso: en cada paso, elegimos el número más grande posible hasta que obtengamos todos los números K.

En este problema, debemos dividir la array de N números en dos subconjuntos de k y N – k números respectivamente. Considere dos casos:

• El subconjunto con la suma más grande, entre estos dos subconjuntos, es un subconjunto de K números. Entonces queremos maximizar la suma en él, ya que la suma en el segundo subconjunto solo disminuirá si la suma en el primer subarreglo aumenta. Así que ahora estamos en el subproblema considerado anteriormente y debemos elegir los k números más grandes.
• El subconjunto con la suma más grande, entre estos dos subconjuntos, es un subconjunto de N – k números. Similar al caso anterior, tenemos que elegir N – k números más grandes entre todos los números.

Ahora, pensemos en cuál de los dos casos anteriores realmente da la respuesta. Podemos ver fácilmente que una diferencia mayor sería cuando se incluyen más números en el grupo de números más grandes. Por lo tanto, podríamos establecer M = max(k, N – k), encontrar la suma de los M números más grandes (que sea S1) y luego la respuesta es S1 – (S – S1), donde S es la suma de todos los números.

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

// C++ program to calculate max_difference between
// the sum of two subset of length k and N - k
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate max_difference
int maxDifference(int arr[], int N, int k)
{
    int M, S = 0, S1 = 0, max_difference = 0;
 
    // Sum of the array
    for (int i = 0; i < N; i++)
        S += arr[i];
 
    // Sort the array in descending order
    sort(arr, arr + N, greater<int>());
    M = max(k, N - k);
    for (int i = 0; i < M; i++)
        S1 += arr[i];
 
    // Calculating max_difference
    max_difference = S1 - (S - S1);
    return max_difference;
}
 
// Driver function
int main()
{
    int arr[] = { 8, 4, 5, 2, 10 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxDifference(arr, N, k) << endl;
    return 0;
}

// Java program to calculate max_difference between
// the sum of two subset of length k and N - k
import java.util.*;
 
class GFG
{
 
// Function to calculate max_difference
static int maxDifference(int arr[], int N, int k)
{
    int M, S = 0, S1 = 0, max_difference = 0;
 
    // Sum of the array
    for (int i = 0; i < N; i++)
        S += arr[i];
    int temp;
     
    // Sort the array in descending order
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            if (arr[i] < arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
 
    M = Math.max(k, N - k);
    for (int i = 0; i < M; i++)
        S1 += arr[i];
 
    // Calculating max_difference
    max_difference = S1 - (S - S1);
    return max_difference;
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 8, 4, 5, 2, 10 };
    int N = arr.length;
    int k = 2;
    System.out.println(maxDifference(arr, N, k));
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 code to calculate max_difference
# between the sum of two subset of
# length k and N - k
 
# Function to calculate max_difference
def maxDifference(arr, N, k ):
    S = 0
    S1 = 0
    max_difference = 0
     
    # Sum of the array
    for i in range(N):
        S += arr[i]
     
    # Sort the array in descending order
    arr.sort(reverse=True)
    M = max(k, N - k)
    for i in range( M):
        S1 += arr[i]
     
    # Calculating max_difference
    max_difference = S1 - (S - S1)
    return max_difference
     
# Driver Code
arr = [ 8, 4, 5, 2, 10 ]
N = len(arr)
k = 2
print(maxDifference(arr, N, k))
 
# This code is contributed by "Sharad_Bhardwaj".

// C# program to calculate max_difference between
// the sum of two subset of length k and N - k
using System;
 
class GFG
{
 
// Function to calculate max_difference
static int maxDifference(int []arr, int N, int k)
{
    int M, S = 0, S1 = 0, max_difference = 0;
 
    // Sum of the array
    for (int i = 0; i < N; i++)
        S += arr[i];
    int temp;
     
    // Sort the array in descending order
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            if (arr[i] < arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
 
    M = Math.Max(k, N - k);
    for (int i = 0; i < M; i++)
        S1 += arr[i];
 
    // Calculating max_difference
    max_difference = S1 - (S - S1);
    return max_difference;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 8, 4, 5, 2, 10 };
    int N = arr.Length;
    int k = 2;
    Console.Write(maxDifference(arr, N, k));
}
}
 
// This code is contributed by mohit kumar 29

<?php
// PHP program to calculate
// max_difference between
// the sum of two subset
// of length k and N - k
 
// Function to calculate
// max_difference
function maxDifference($arr, $N, $k)
{
    $M; $S = 0; $S1 = 0;
    $max_difference = 0;
 
    // Sum of the array
    for ($i = 0; $i < $N; $i++)
        $S += $arr[$i];
 
    // Sort the array in
    // descending order
    rsort($arr);
    $M = max($k, $N - $k);
    for ($i = 0; $i < $M; $i++)
        $S1 += $arr[$i];
 
    // Calculating
    // max_difference
    $max_difference = $S1 - ($S - $S1);
    return $max_difference;
}
 
// Driver Code
$arr = array(8, 4, 5, 2, 10);
$N = count($arr);
$k = 2;
echo maxDifference($arr, $N, $k);
 
// This code is contributed
// by anuj_67.
?>

<script>
 
// Javascript program to calculate max_difference
// between the sum of two subset of length
// k and N - k
 
// Function to calculate max_difference
function maxDifference(arr, N, k)
{
    let M, S = 0, S1 = 0, max_difference = 0;
 
    // Sum of the array
    for(let i = 0; i < N; i++)
        S += arr[i];
         
    let temp;
 
    // Sort the array in descending order
    for(let i = 0; i < N; i++)
    {
        for(let j = i + 1; j < N; j++)
        {
            if (arr[i] < arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
 
    M = Math.max(k, N - k);
    for(let i = 0; i < M; i++)
        S1 += arr[i];
 
    // Calculating max_difference
    max_difference = S1 - (S - S1);
    return max_difference;
}
 
// Driver code
let arr = [ 8, 4, 5, 2, 10 ];
let N = arr.length;
let k = 2;
 
document.write(maxDifference(arr, N, k));
 
// This code is contributed by divyeshrabadiya07
 
</script>

17

Complejidad de tiempo: O(N log N) , para ordenar la array 
Espacio auxiliar: O(1) , ya que no se utiliza espacio adicional

Optimizaciones adicionales: podemos usar Heap (o cola de prioridad) para encontrar M elementos más grandes de manera eficiente. Consulte k elementos más grandes (o más pequeños) en una array para obtener detalles.