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 maximizedvoid 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 codeint 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 approachclass 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 maximizeddef 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 codearr = [-1, 1, 2, -3, 2, 2]n = len(arr)k = 3maxSumArr(arr, n, k) |
C#
// C# implementation of the above approachusing 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/maximum-sum-after-k-consecutive-deletions/ […]
… [Trackback]
[…] Here you will find 28023 more Info on that Topic: geeksforgeeks.org/maximum-sum-after-k-consecutive-deletions/ […]