Eliminar k elementos de esquina para maximizar la suma restante

Dada una array, la tarea es eliminar el total de k elementos de las esquinas para maximizar la suma de los elementos restantes. Por ejemplo, si k = 5 y eliminamos 2 elementos de la esquina izquierda, entonces debemos eliminar 3 elementos de la esquina derecha.
Ejemplos: 

Entrada : arr = [11, 49, 100, 20, 86, 29, 72], k = 4 
Salida : 206 
Explicación : Eliminamos 29 y 72 de la esquina derecha. También eliminamos 11 y 49 de la esquina izquierda para obtener la suma máxima de 206 para los elementos restantes.

Entrada : arr[] = [1, 2, 3, 4, 5, 6, 1], k = 3 
Salida: 18 
Explicación: Eliminamos dos elementos de la esquina izquierda (1 y 2) y un elemento de la esquina derecha ( 1). 

Enfoque ingenuo: 
1) Inicializar el resultado como infinito negativo. 
2) Calcular la suma total. 
3) Ejecute un ciclo para x = 1 a k 
…..Elimine los elementos ‘x’ del lado izquierdo y los elementos k – i del lado derecho. 
…..Si los elementos restantes tienen una suma mayor que el resultado, actualice el resultado.

Complejidad de tiempo: O(n * k)
Enfoque eficiente (usando la técnica de deslizamiento de ventanas ) 
1) Encuentre la suma de los primeros nk elementos e inicialícelos como suma actual y también inicialícelos como resultado. 
2) Ejecute un bucle para i = nk a n-1 
….curr_sum = curr_sum – arr[i – n + k] + arr[i] 
….res = max(res, curr_sum)
En el paso 2, ejecutamos principalmente deslizamiento ventana. Eliminamos un elemento del lado izquierdo y agregamos un elemento del lado derecho.

A continuación se muestra la implementación en C++ de la declaración del problema anterior.

#include <bits/stdc++.h>
using namespace std;
int calculate(int arr[], int n, int k)
{
    // Calculate the sum of all elements
    // excluding the last k elements..
    int curr_sum = 0;
    for (int i = 0; i < n - k; i++)
        curr_sum += arr[i];
 
    // now here its time to use sliding window
    // concept, remove the first element from
    // the current window and add the new element
    // in it in order to get the sum of all n-k size
    // of elements in arr.
    // Calculate the minimum sum of elements of
    // size n-k and stored it into the result
    int res = curr_sum;
    for (int i = n - k; i < n; i++) {
        curr_sum = curr_sum - arr[i - n + k] + arr[i];
        res = max(res, curr_sum);
    }
 
    // Now return result (sum of remaining n-k elements)
    return res;
}
 
// main function
int main()
{
    int arr[] = { 11, 49, 100, 20, 86, 29, 72 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    cout << "Maximum sum of remaining elements "
         << calculate(arr, n, k) << "\n";
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
static int calculate(int[] arr,
                     int n, int k)
{
  // Calculate the total
  // sum of all elements
  // present in the array..
  int total_sum = 0;
   
  for (int i = 0; i < n; i++)
    total_sum += arr[i];
 
  // Now calculate the sum
  // of all elements excluding
  // the last k elements..
  int curr_sum = 0;
   
  for (int i = 0; i < n - k; i++)
    curr_sum += arr[i];
 
  // Now here its time to use
  // sliding window concept,
  // remove the first element
  // from the current window
  // and add the new element
  // in it in order to get
  // the sum of all n-k size
  // of elements in arr.
  // Calculate the minimum
  // sum of elements of
  // size n-k and stored it
  // into the result
  int res = curr_sum;
   
  for (int i = n - k; i < n; i++)
  {
    curr_sum = curr_sum -
               arr[i - n + k] +
               arr[i];
    res = Math.max(res, curr_sum);
  }
 
  // Now return result (sum of
  // remaining n-k elements)
  return res;
}
 
// Driver code
public static void main(String[] args)
{
  int[] arr = {11, 49, 100,
               20, 86, 29, 72};
  int n = arr.length;
  int k = 4;
  System.out.print("Maximum sum of remaining " +
                   "elements " +
                    calculate(arr, n, k) + "\n");
}
}
 
// This code is contributed by Chitranayal

def calculate(arr, n, k):
     
    # calculate the total sum of all elements
    # present in the array..
    total_sum = 0
    for i in arr:
        total_sum += i
 
    # now calculate the sum of all elements
    # excluding the last k elements..
    curr_sum = 0
    for i in range(n - k):
        curr_sum += arr[i]
 
    # now here its time to use sliding window
    # concept, remove the first element from
    # the current window and add the new element
    # in it in order to get the sum of all n-k size
    # of elements in arr.
    # Calculate the minimum sum of elements of
    # size n-k and stored it into the result
    res = curr_sum
    for i in range(n - k, n):
        curr_sum = curr_sum - arr[i - n + k] + arr[i]
        res = max(res, curr_sum)
 
    # Now return result (sum of remaining n-k elements)
    return res
 
# main function
if __name__ == '__main__':
    arr=[11, 49, 100, 20, 86, 29, 72]
    n = len(arr)
    k = 4
    print("Maximum sum of remaining elements ",calculate(arr, n, k))
 
# This code is contributed by mohit kumar 29   

using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
   
static int calculate(int []arr, int n, int k)
{
     
    // Calculate the total sum of all elements
    // present in the array..
    int total_sum = 0;
    for(int i = 0; i < n; i++)
        total_sum += arr[i];
  
    // Now calculate the sum of all elements
    // excluding the last k elements..
    int curr_sum = 0;
    for(int i = 0; i < n - k; i++)
        curr_sum += arr[i];
  
    // Now here its time to use sliding window
    // concept, remove the first element from
    // the current window and add the new element
    // in it in order to get the sum of all n-k size
    // of elements in arr.
    // Calculate the minimum sum of elements of
    // size n-k and stored it into the result
    int res = curr_sum;
    for(int i = n - k; i < n; i++)
    {
        curr_sum = curr_sum -
                  arr[i - n + k] + arr[i];
        res = Math.Max(res, curr_sum);
    }
  
    // Now return result (sum of
    // remaining n-k elements)
    return res;
}
 
// Driver code
public static void Main(string[] args)
{
    int []arr = { 11, 49, 100, 20, 86, 29, 72 };
    int n = arr.Length;
    int k = 4;
     
    Console.Write("Maximum sum of remaining " +
                  "elements " +
                  calculate(arr, n, k) + "\n");
}
}
 
// This code is contributed by rutvik_56

<script>
 
function calculate(arr, n, k)
{
 
    // calculate the total sum of all elements
    // present in the array..
    let total_sum = 0;
    for (let i = 0; i < n; i++)
        total_sum += arr[i];
 
    // now calculate the sum of all elements
    // excluding the last k elements..
    let curr_sum = 0;
    for (let i = 0; i < n - k; i++)
        curr_sum += arr[i];
 
    // now here its time to use sliding window
    // concept, remove the first element from
    // the current window and add the new element
    // in it in order to get the sum of all n-k size
    // of elements in arr.
    // Calculate the minimum sum of elements of
    // size n-k and stored it into the result
    let res = curr_sum;
    for (let i = n - k; i < n; i++) {
        curr_sum = curr_sum - arr[i - n + k] + arr[i];
        res = Math.max(res, curr_sum);
    }
 
    // Now return result (sum of remaining n-k elements)
    return res;
}
 
// main function
let arr = [11, 49, 100, 20, 86, 29, 72];
let n = arr.length;
let k = 4;
document.write("Maximum sum of remaining elements " + calculate(arr, n, k) + "<br>");
 
// This code is contributed by gfgking
</script>

Maximum sum of remaining elements 206

Complejidad temporal: O(k) 
Espacio auxiliar: O(1)