Diferencia máxima entre el grupo de k-elementos y el resto de la array.

Se le da una array de n elementos. Debe dividir la array dada en dos grupos, de modo que un grupo consista exactamente en k elementos y el segundo grupo consista en el resto de elementos. Tu resultado debe ser la máxima diferencia posible de la suma de los elementos de estos dos grupos.

Ejemplos: 

Input : arr[n] = {1, 5, 2, 6, 3}  , k = 2
Output : Maximum Difference = 11
Explanation : group1 = 1+2 , group2 = 3+5+6
              Maximum Difference = 14 - 3 = 11

Input : arr[n] = {1, -1, 3, -2, -3} , k = 2
Output : Maximum Difference = 10
Explanation : group1 = -1-2-3 , group2 = 1+3
              Maximum Difference = 4 - (-6) = 10

Para encontrar la máxima diferencia de grupo tenemos dos posibilidades. Para el primer caso k-los elementos más pequeños pertenecen a un grupo y los demás elementos a otro grupo. Para el segundo caso, los elementos k-más grandes pertenecen a un grupo y los demás elementos a otro grupo. 
Entonces, en primer lugar, ordene toda la array y encuentre la diferencia de grupo para ambos casos explicados anteriormente y luego, finalmente, encuentre la diferencia máxima entre ellos. 

Algoritmo: 

    sort the arrayfind sum of whole array
case-1    -> find sum of first k-smallest elements
    -> differece1 = abs( arraySum - 2*k_Smallest)
case-2    -> find sum of first k-largest elements
    -> differece2 = abs( arraySum - 2*k_largest)
 print max(difference1, difference2)

Implementación:

// CPP to find maximum group difference
#include<bits/stdc++.h>
using namespace std;
 
// utility function for array sum
long long int arraySum(int arr[], int n)
{
    long long int sum = 0;
    for (int i=0; i<n; i++)
        sum = sum + arr[i];
    return sum;
}
 
// function for finding
// maximum group difference of array
long long int maxDiff (int arr[], int n, int k)
{
    // sort the array
    sort(arr, arr+n);
 
    // find array sum
    long long int arraysum = arraySum(arr, n);
     
    // difference for k-smallest
    // diff1 = (arraysum-k_smallest)-k_smallest
    long long int diff1 = abs(arraysum - 2*arraySum(arr, k));
     
    // reverse array for finding sum 0f 1st k-largest
    reverse(arr, arr+n);
     
    // difference for k-largest
    // diff2 = (arraysum-k_largest)-k_largest
    long long int diff2 = abs(arraysum - 2*arraySum(arr, k));
     
    // return maximum difference value
    return(max(diff1,diff2));
 
}
 
// driver program
int main()
{
    int arr[] = {1, 7, 4, 8, -1, 5, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << "Maximum Difference = " << maxDiff(arr,n,k);
    return 0;
}

// java to find maximum group difference
import java.util.Arrays;
 
public class GFG {
     
    // utility function for array sum
    static long arraySum(int arr[], int n)
    {
        long sum = 0;
        for (int i = 0; i < n; i++)
            sum = sum + arr[i];
             
        return sum;
    }
     
    // function for finding maximum group
    // difference of array
    static long maxDiff (int arr[], int n, int k)
    {
         
        // sort the array
        Arrays.sort(arr);
     
        // find array sum
        long arraysum = arraySum(arr, n);
         
        // difference for k-smallest
        // diff1 = (arraysum-k_smallest)-k_smallest
        long diff1 = Math.abs(arraysum -
                            2 * arraySum(arr, k));
         
        // reverse array for finding sum of
        // 1st k-largest
        int end = arr.length - 1;
        int start = 0;
        while (start < end)
        {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
 
        // difference for k-largest
        // diff2 = (arraysum-k_largest)-k_largest
        long diff2 = Math.abs(arraysum -
                            2 * arraySum(arr, k));
         
        // return maximum difference value
        return(Math.max(diff1, diff2));
     
    }
     
    public static void main(String args[]) {
        int arr[] = {1, 7, 4, 8, -1, 5, 2, 1};
        int n = arr.length;
        int k = 3;
         
        System.out.println("Maximum Difference = "
                            + maxDiff(arr, n, k));
 
    }
}
 
// This code is contributed by Sam007.

# Python3 to find maximum group difference
 
# utility function for array sum
def arraySum(arr, n):
 
    sum = 0
    for i in range(n):
        sum = sum + arr[i]
    return sum
 
# function for finding
# maximum group difference of array
def maxDiff (arr, n, k):
     
    # sort the array
    arr.sort()
 
    # find array sum
    arraysum = arraySum(arr, n)
     
    # difference for k-smallest
    # diff1 = (arraysum-k_smallest)-k_smallest
    diff1 = abs(arraysum - 2 * arraySum(arr, k))
     
    # reverse array for finding sum
    # 0f 1st k-largest
    arr.reverse()
     
    # difference for k-largest
    # diff2 = (arraysum-k_largest)-k_largest
    diff2 = abs(arraysum - 2 * arraySum(arr, k))
     
    # return maximum difference value
    return(max(diff1, diff2))
 
# Driver Code
if __name__ == "__main__":
    arr = [1, 7, 4, 8, -1, 5, 2, 1]
    n = len(arr)
    k = 3
    print ("Maximum Difference =",
               maxDiff(arr, n, k))
     
# This code is contributed by ita_c

// C# to find maximum group difference
using System;
 
public class GFG {
     
    // utility function for array sum
    static long arraySum(int []arr, int n)
    {
        long sum = 0;
        for (int i = 0; i < n; i++)
            sum = sum + arr[i];
             
        return sum;
    }
     
    // function for finding maximum group
    // difference of array
    static long maxDiff (int []arr, int n, int k)
    {
         
        // sort the array
        Array.Sort(arr);
     
        // find array sum
        long arraysum = arraySum(arr, n);
         
        // difference for k-smallest
        // diff1 = (arraysum-k_smallest)-k_smallest
        long diff1 = Math.Abs(arraysum -
                             2 * arraySum(arr, k));
         
        // reverse array for finding sum of
        // 1st k-largest
        Array.Reverse(arr);
         
        // difference for k-largest
        // diff2 = (arraysum-k_largest)-k_largest
        long diff2 = Math.Abs(arraysum -
                            2 * arraySum(arr, k));
         
        // return maximum difference value
        return(Math.Max(diff1, diff2));
     
    }
     
    // Driver program
    static public void Main ()
    {
        int []arr = {1, 7, 4, 8, -1, 5, 2, 1};
        int n = arr.Length;
        int k = 3;
         
        Console.WriteLine("Maximum Difference = "
                           + maxDiff(arr, n, k));
    }
}
 
// This Code is contributed by vt_m.

<?php
// PHP to find maximum group difference
 
// utility function for array sum
function arraySum($arr, $n)
{
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum = $sum + $arr[$i];
    return $sum;
}
 
// function for finding
// maximum group difference
// of array
function maxDiff ($arr, $n, $k)
{
     
    // sort the array
    sort($arr);
 
    // find array sum
    $arraysum = arraySum($arr, $n);
     
    // difference for k-smallest
    // diff1 = (arraysum - k_smallest)
    // - k_smallest
    $diff1 = abs($arraysum - 2 *
             arraySum($arr, $k));
     
    // reverse array for finding
    // sum 0f 1st k-largest
    array_reverse($arr);
     
    // difference for k-largest
    // diff2 = (arraysum - k_largest)
    // - k_largest
    $diff2 = abs($arraysum - 2 *
             arraySum($arr, $k));
     
    // return maximum difference value
    return(max($diff1,$diff2));
 
}
 
    // Driver Code
    $arr = array(1, 7, 4, 8, -1, 5, 2, 1);
    $n = count($arr);
 
    $k = 3;
    echo "Maximum Difference = " ,
          maxDiff($arr, $n, $k);
 
// This Code is contributed by vt_m.
?>

<script>
 
// Javascript to find maximum group difference
 
// utility function for array sum
function arraySum(arr, n)
{
    var sum = 0;
    for (var i=0; i<n; i++)
        sum = sum + arr[i];
    return sum;
}
 
// function for finding
// maximum group difference of array
function maxDiff (arr, n, k)
{
    // sort the array
    arr.sort((a,b)=>a-b);
 
    // find array sum
    var arraysum = arraySum(arr, n);
     
    // difference for k-smallest
    // diff1 = (arraysum-k_smallest)-k_smallest
    var diff1 = Math.abs(arraysum - 2*arraySum(arr, k));
     
    // reverse array for finding sum 0f 1st k-largest
    arr.reverse();
     
    // difference for k-largest
    // diff2 = (arraysum-k_largest)-k_largest
    var diff2 = Math.abs(arraysum - 2*arraySum(arr, k));
     
    // return maximum difference value
    return(Math.max(diff1,diff2));
 
}
 
// driver program
var arr = [1, 7, 4, 8, -1, 5, 2, 1];
var n = arr.length;
var k = 3;
document.write( "Maximum Difference = " + maxDiff(arr,n,k));
 
</script>

Maximum Difference = 25

Complejidad de Tiempo: O(n log n) 
Espacio Auxiliar: O(1)

Optimizaciones a la solución anterior: 

1. Podemos evitar invertir la array y encontrar la suma de k elementos desde el final usando un ciclo diferente. 
2. También podemos encontrar la suma de k elementos más grandes y más pequeños de manera más eficiente utilizando los métodos discutidos en las publicaciones a continuación. 

K’th elemento más pequeño/más grande en array no ordenada | Conjunto 2 (Tiempo lineal esperado)  
K’th Elemento más pequeño/más grande en array no ordenada | Conjunto 3 (Tiempo lineal en el peor de los casos)

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.