Maximum sum after K consecutive deletions

0 0 5 minutes read

Given an array arr[] of size N and an integer K, the task is to delete K continuous elements from the array such that the sum of the remaining element is maximum. Here we need to print the remaining elements of the array.

Examples:

Input: arr[] = {-1, 1, 2, -3, 2, 2}, K = 3
Output: -1 2 2
Delete 1, 2, -3 and the sum of the remaining
elements will be 3 which is maximum possible.

Input: arr[] = {1, 2, -3, 4, 5}, K = 1
Output: 1 2 4 5

Approach: Calculate the sum of k-consecutive elements and remove the elements with the minimum sum. Print the rest of the elements of the array.

Below is the implementation of the above approach:

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>

Output:

-1 2 2

Time Complexity: O(n)
Auxiliary space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!