Dada una array arr[] de tamaño N y un número entero K , la tarea es eliminar K elementos continuos de la array de modo que la suma del elemento restante sea máxima. Aquí necesitamos imprimir los elementos restantes de la array.
Ejemplos:
Entrada: arr[] = {-1, 1, 2, -3, 2, 2}, K = 3
Salida: -1 2 2
Elimine 1, 2, -3 y la suma de los
elementos restantes será 3, que es máximo posible.
Entrada: arr[] = {1, 2, -3, 4, 5}, K = 1
Salida: 1 2 4 5
Enfoque: Calcule la suma de k elementos consecutivos y elimine los elementos con la suma mínima. Imprime el resto de los elementos de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the array after removing
// k consecutive elements such that the sum
// of the remaining elements is maximized
void maxSumArr(int arr[], int n, int k)
{
int cur = 0, index = 0;
// Find the sum of first k elements
for (int i = 0; i < k; i++)
cur += arr[i];
// To store the minimum sum of k
// consecutive elements of the array
int min = cur;
for (int i = 0; i < n - k; i++) {
// Calculating sum of next k elements
cur = cur - arr[i] + arr[i + k];
// Update the minimum sum so far and the
// index of the first element
if (cur < min) {
cur = min;
index = i + 1;
}
}
// Printing result
for (int i = 0; i < index; i++)
cout << arr[i] << " ";
for (int i = index + k; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { -1, 1, 2, -3, 2, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
maxSumArr(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to print the array after removing
// k consecutive elements such that the sum
// of the remaining elements is maximized
static void maxSumArr(int arr[], int n, int k)
{
int cur = 0, index = 0;
// Find the sum of first k elements
for (int i = 0; i < k; i++)
cur += arr[i];
// To store the minimum sum of k
// consecutive elements of the array
int min = cur;
for (int i = 0; i < n - k; i++) {
// Calculating sum of next k elements
cur = cur - arr[i] + arr[i + k];
// Update the minimum sum so far and the
// index of the first element
if (cur < min) {
cur = min;
index = i + 1;
}
}
// Printing result
for (int i = 0; i < index; i++)
System.out.print(arr[i] + " ");
for (int i = index + k; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -1, 1, 2, -3, 2, 2 };
int n = arr.length;
int k = 3;
maxSumArr(arr, n, k);
}
}
Python
# Python3 implementation of the approach # Function to print the array after removing # k consecutive elements such that the sum # of the remaining elements is maximized def maxSumArr(arr, n, k): cur = 0 index = 0 # Find the sum of first k elements for i in range(k): cur += arr[i] # To store the minimum sum of k # consecutive elements of the array min = cur; for i in range(n-k): # Calculating sum of next k elements cur = cur-arr[i]+arr[i + k] # Update the minimum sum so far and the # index of the first element if(cur<min): cur = min index = i + 1 # Printing result for i in range(index): print(arr[i], end =" ") i = index + k while i<n: print(arr[i], end =" ") i += 1 # Driver code arr = [-1, 1, 2, -3, 2, 2] n = len(arr) k = 3 maxSumArr(arr, n, k)
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to print the array after removing
// k consecutive elements such that the sum
// of the remaining elements is maximized
static void maxSumArr(int []arr, int n, int k)
{
int cur = 0, index = 0;
// Find the sum of first k elements
for (int i = 0; i < k; i++)
cur = cur + arr[i];
// To store the minimum sum of k
// consecutive elements of the array
int min = cur;
for (int i = 0; i < n - k; i++)
{
// Calculating sum of next k elements
cur = (cur - arr[i]) + (arr[i + k]);
// Update the minimum sum so far and the
// index of the first element
if (cur < min)
{
cur = min;
index = i + 1;
}
}
// Printing result
for (int i = 0; i < index; i++)
Console.Write(arr[i] + " ");
for (int i = index + k; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
static public void Main ()
{
int []arr = { -1, 1, 2, -3, 2, 2 };
int n = arr.Length;
int k = 3;
maxSumArr(arr, n, k);
}
}
// This code is contributed by ajit..
Javascript
<script>
// Javascript implementation of the above approach
// Function to print the array after removing
// k consecutive elements such that the sum
// of the remaining elements is maximized
function maxSumArr(arr, n, k)
{
let cur = 0, index = 0;
// Find the sum of first k elements
for (let i = 0; i < k; i++)
cur = cur + arr[i];
// To store the minimum sum of k
// consecutive elements of the array
let min = cur;
for (let i = 0; i < n - k; i++)
{
// Calculating sum of next k elements
cur = (cur - arr[i]) + (arr[i + k]);
// Update the minimum sum so far and the
// index of the first element
if (cur < min)
{
cur = min;
index = i + 1;
}
}
// Printing result
for (let i = 0; i < index; i++)
document.write(arr[i] + " ");
for (let i = index + k; i < n; i++)
document.write(arr[i] + " ");
}
let arr = [ -1, 1, 2, -3, 2, 2 ];
let n = arr.length;
let k = 3;
maxSumArr(arr, n, k);
</script>
Producción:
-1 2 2
Complejidad de tiempo: O(n)