Maximice la diferencia entre los elementos de array máximos y mínimos después de K operaciones

Dada una array arr[] de tamaño N y un entero positivo K , la tarea es encontrar la diferencia máxima entre el elemento más grande y el elemento más pequeño en la array incrementando o disminuyendo los elementos de la array en 1 , K veces.

Ejemplos:

Entrada: arr[] = {7, 7, 7, 7}, K = 1
Salida: 14
Explicación: Decrementar el valor de arr[0] e incrementar el valor de arr[3] en 7 modifica arr[] = {0 , 7, 7, 14}. Por lo tanto, la diferencia máxima entre el elemento más grande y el elemento más pequeño de la array es 14

Entrada: arr[] = {0, 0, 0, 0, 0}, K = 2
Salida: 0
Explicación: dado que todos los elementos de la array son 0, la disminución de cualquier elemento de la array hace que ese elemento sea menor que 0. Por lo tanto, la salida requerida es 0.

Enfoque: siga los pasos a continuación para resolver el problema:

• Ordene la array en orden descendente .
• Recorra la array y calcule la suma de los primeros K elementos más grandes.
• Finalmente, imprima la suma de los primeros K los elementos más grandes de la array.

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum difference
// between the maximum and minimum in the
// array after K operations
int maxDiffLargSmallOper(int arr[],
                         int N, int K)
{
    // Stores maximum difference between
    // largest  and smallest array element
    int maxDiff = 0;
 
    // Sort the array in descending order
    sort(arr, arr + N, greater<int>());
 
    // Traverse the array arr[]
    for (int i = 0; i <= min(K, N - 1);
         i++) {
 
        // Update maxDiff
        maxDiff += arr[i];
    }
 
    return maxDiff;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 7, 7, 7, 7 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
    int K = 1;
    cout << maxDiffLargSmallOper(arr, N, K);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Reverse array
static int[] reverse(int a[])
{
    int i, n = a.length, t;
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
 
// Function to find the maximum difference
// between the maximum and minimum in the
// array after K operations
static int maxDiffLargSmallOper(int arr[],
                                int N, int K)
{
     
    // Stores maximum difference between
    // largest  and smallest array element
    int maxDiff = 0;
 
    // Sort the array in descending order
    Arrays.sort(arr);
    arr = reverse(arr);
     
    // Traverse the array arr[]
    for(int i = 0; i <= Math.min(K, N - 1); i++)
    {
         
        // Update maxDiff
        maxDiff += arr[i];
    }
     
    return maxDiff;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 7, 7, 7, 7 };
    int N = arr.length;
    int K = 1;
     
    System.out.print(maxDiffLargSmallOper(arr, N, K));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to find the maximum difference
# between the maximum and minimum in the
# array after K operations
def maxDiffLargSmallOper(arr, N, K):
     
     
    # Stores maximum difference between
    # largest  and smallest array element
    maxDiff = 0;
     
    # Sort the array in descending order
    arr.sort(reverse = True);
     
     
    # Traverse the array arr[]
    for i  in  range(min(K + 1, N)):
         
        # Update maxDiff
        maxDiff += arr[i];
     
    return maxDiff;
 
# Driver Code
if __name__ == "__main__": 
 
    arr = [ 7, 7, 7, 7 ];
    N = len(arr)
    K = 1;
    print(maxDiffLargSmallOper(arr, N, K));

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find the maximum difference
// between the maximum and minimum in the
// array after K operations
static int maxDiffLargSmallOper(int []arr, int N,
                                int K)
{
     
    // Stores maximum difference between
    // largest and smallest array element
    int maxDiff = 0;
 
    // Sort the array in descending order
    Array.Sort(arr);
    Array.Reverse(arr);
     
    // Traverse the array arr[]
    for(int i = 0; i <= Math.Min(K, N - 1); i++)
    {
         
        // Update maxDiff
        maxDiff += arr[i];
    }
    return maxDiff;
}
 
// Driver code
public static void Main()
{
    int [] arr = new int[]{ 7, 7, 7, 7 };
    int N = arr.Length;
    int K = 1;
     
    Console.Write(maxDiffLargSmallOper(arr, N, K));
}
}
 
// This code is contributed by mohit kumar 29

<script>
 
// Javascript program to implement
// the above approach
 
// Reverse array
function reverse(a)
{
    var i, n = a.length, t;
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
 
// Function to find the maximum difference
// between the maximum and minimum in the
// array after K operations
function maxDiffLargSmallOper(arr, N, K)
{
     
    // Stores maximum difference between
    // largest and smallest array element
    var maxDiff = 0;
 
    // Sort the array in descending order
    arr.sort();
    arr = reverse(arr);
 
    // Traverse the array arr
    for(i = 0; i <= Math.min(K, N - 1); i++)
    {
         
        // Update maxDiff
        maxDiff += arr[i];
    }
    return maxDiff;
}
 
// Driver Code
var arr = [ 7, 7, 7, 7 ];
var N = arr.length;
var K = 1;
 
document.write(maxDiffLargSmallOper(arr, N, K));
 
// This code is contributed by aashish1995
 
</script>

14

Complejidad de tiempo: O(N * log(N))  
Espacio auxiliar: O(1)