Remove K Corner Elements
Posted: 31 Jul, 2021
Difficulty: Easy
Given an array ‘arr’ consisting of ‘N’ integer elements. You have to remove ‘K’ elements from the beginning or end of the array. Return the maximum possible sum of the remaining array elements.
Note: you can remove elements from both beginning and end, but a total of ‘K’ elements must be removed.
Example :
If N = 7 and K = 3, and the input array is:
{1, 2, 3, 4, 5, 6, 7}
After removing the first three elements, the resulting array now becomes {4, 5, 6, 7} and the sum of the remaining array is equal to 22.
Removing any other combination of three elements will always result in the remaining array sum less than 22.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains two integers ‘N’ and ‘K’, where N denotes the length of the given array and K denotes the number of elements to be removed.
The next line of each test case contains N integers denoting array elements ‘arr[i]’.
Output Format :
For each test case print a single integer denoting the maximum sum of the remaining array.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
0 <= K <= N
0 <= arr[i] <=10^6
Time limit: 1 sec
Sample Input 1 :
2
6 3
1 2 6 4 5 3
8 4
5 3 1 1 8 8 2 2
Sample Output 1 :
15
20
Explanation Of Sample Output 1 :
For test case 1 :
After removing two elements from the beginning and one element from the end, the original array now becomes {6, 4, 5}. The remaining elements of the array have a sum equal to 15.
For test case 2 :
After removing four elements from the beginning, the original array now becomes {8, 8, 2, 2}. The remaining elements of the array have a sum equal to 20.
Sample Input 2 :
2
5 5
4 5 7 2 3
5 0
1 2 3 4 5
Sample Output 2 :
0
15
Approach 1
For each possible combination of removing elements from the array, calculate the sum of the remaining elements. Finally, return the maximum sum calculated over all the possible ways.
The steps are as follows:
- Initialize ans = 0.
- Run a for loop for stPos from 0 to K.
- Calculate the sum of array from stPos to N - 1 - (K - stPos).
- If sum is greater than ans, then set ans equal to the value of sum.
- Return the final value of ans.
Approach 2
Consider a window of size equal to N- K, for each possible window of this size we can find the sum, and return the maximum possible sum found.
The steps are as follows:
- Initialize ans equal to 0.
- The initial window starts from st = 0 and ends at en = N - K - 1.
- Calculate the sum windowSum of the initial window.
- Run a while loop till condition en is less than N is satisfied.
- For each iteration deduct arr[st]. Increment value of st and en and add arr[en] to windowSum, windowSum now stores the sum of the new window from st to en.
- If windowSum is greater than ans, then store the current value of windowSum in ans.
- Return the final value of ans.
SIMILAR PROBLEMS
Two Sum II - Input Array Is Sorted
Posted: 4 Mar, 2022
Difficulty: Moderate
Ninja And Matrix
Posted: 12 Apr, 2022
Difficulty: Easy
Ninja In Interview
Posted: 13 Apr, 2022
Difficulty: Easy
Missing Number
Posted: 17 Apr, 2022
Difficulty: Easy
Min Heap
Posted: 5 May, 2022
Difficulty: Moderate