Maximice la suma de las diferencias de elementos consecutivos después de eliminar exactamente K elementos

Dada una array ordenada arr[] de longitud N y un entero K tal que K < N , la tarea es eliminar exactamente K elementos de la array de modo que la suma de las diferencias de los elementos consecutivos de la array se maximice.
Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4}, K = 1 
Salida: 3 
Consideremos todos los casos posibles: 
a) Quitar arr[0]: arr[] = {2, 3, 4}, ans = 2 
b) Eliminar arr[1]: arr[] = {1, 3, 4}, respuesta = 3 
c) Eliminar arr[2]: arr[] = {1, 2, 4}, respuesta = 3 
d) Eliminar arr[3]: arr[] = {1, 2, 3}, ans = 2 
3 es el máximo de todas las respuestas.
Entrada: arr[] = {1, 2, 10}, K = 2 
Salida: 0 

Planteamiento: Hay dos casos:  

1. Si K < N – 1 , la respuesta será arr[N – 1] – arr[0] . Esto se debe a que cualquier K elemento de los N – 2 elementos internos de la array se puede eliminar sin afectar la suma de diferencias maximizada. Por ejemplo, si se debe eliminar cualquier elemento individual de 1, 2, 3 y 4, no importa si se elimina 2 o 3, la suma final de la diferencia seguirá siendo la misma, es decir ((3 – 1) + (4 – 3)) = 3 que es igual a ((2 – 1) + (4 – 2)) = 3.
2. Si K = N – 1 , la respuesta será 0 porque solo queda un elemento que es tanto el mínimo como el máximo. Por lo tanto, la respuesta es 0 .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximized sum
int findSum(int* arr, int n, int k)
{
 
    // Remove any k internal elements
    if (k <= n - 2)
        return (arr[n - 1] - arr[0]);
 
    return 0;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(int);
    int k = 1;
 
    cout << findSum(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the maximized sum
    static int findSum(int []arr, int n, int k)
    {
     
        // Remove any k internal elements
        if (k <= n - 2)
            return (arr[n - 1] - arr[0]);
     
        return 0;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 1, 2, 3, 4 };
        int n = arr.length;
        int k = 1;
     
        System.out.println(findSum(arr, n, k));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the maximized sum
def findSum(arr, n, k) :
 
    # Remove any k internal elements
    if (k <= n - 2) :
        return (arr[n - 1] - arr[0]);
         
    return 0;
     
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 3, 4 ];
    n = len(arr);
    k = 1;
 
    print(findSum(arr, n, k));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the maximized sum
    static int findSum(int []arr,
                       int n, int k)
    {
     
        // Remove any k internal elements
        if (k <= n - 2)
            return (arr[n - 1] - arr[0]);
     
        return 0;
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 1, 2, 3, 4 };
        int n = arr.Length;
        int k = 1;
     
        Console.WriteLine(findSum(arr, n, k));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximized sum
function findSum(arr, n, k)
{
 
    // Remove any k internal elements
    if (k <= n - 2)
        return (arr[n - 1] - arr[0]);
 
    return 0;
}
 
// Driver code
var arr = [1, 2, 3, 4];
var n = arr.length;
var k = 1;
document.write( findSum(arr, n, k));
 
</script>

3

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)