Maximize Score

PROBLEM STATEMENT

You are given an array ‘arr’ of size ‘N’. Your task is to maximize your score by doing the following operation at most ‘K’ – times.

1. Choose an element from the start or end of the array and the value of the element to your score.
2. Remove the element from the array you have chosen in step – 1.

Note:

Initially, you have a score of zero.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’, denoting the length of the array and the maximum number of operations you can make respectively.
The second line of each test case contains ‘N’ space-separated integers denoting the values of array elements.

Output Format:

For each test case, print the maximum score you can make.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 5
1 <= N <= 5000
1 <= K <= N
1 <= arr[ i ]  <= 10^5

Where ‘T’ is the number of test cases, ‘N’  is the size of the array, ‘K’ is the maximum number of operations you can make, and ‘arr[ i ]’ is the value of the ith element of the array.

Time Limit: 1 sec

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Approach 1

The idea here is to think about the problem in the reverse direction. We need to take exactly ‘K’ elements from the array. So we need to select some elements from the starting of the array and some from the ending of the array and the total number of elements chosen from starting and ending of the array must be ‘K’. This line implies that we need to skip ‘N – K’ elements from the array and these ‘N – K’ elements must form a subarray.

So our problem reduces to finding the subarray of size ‘N – K’ such that the sum of the subarray is minimum. We will generate all subarrays of size ‘N – K’ and try to find the subarray of having a minimum sum. Then we will subtract this from the sum of the array to get the answer.

Algorithm:

Calculate the sum of the array and store it in the ‘sum’ variable.
Declare a variable ‘minSum’ that stores the minimum sum of the subarray of size ‘N – K’ and initialize it with ‘sum’. Also declare a variable ‘cur’ to keep track of the sum in the current subarray of size ‘N – K’.
Run a loop from 0 to ‘K’.
Run a loop to calculate the sum of the subarray starting from index ‘i’ having size ‘N – K’ and store it in ‘’cur’.
If ‘minSum’ is greater than ‘cur’ then update ‘minSum’ with ‘cur’.
Return ‘sum’ – ‘minSum’ as this is the maximum score we can make.

Try Problem

Approach 2

As discussed in the previous approach our problem reduces to finding the subarray of size ‘N – K’ such that the sum of the subarray is minimum. We will maintain a window of size ‘N – K’ to find the required subarray sum. Then we will subtract this from the sum of the array to get the answer.

Algorithm:

Calculate the sum of the array and store it in the ‘sum’ variable.
Declare a variable ‘minSum’ that stores the minimum sum of the subarray of size ‘N – K’ and initialize it with ‘sum’. Also declare a variable ‘cur’ to keep track of the sum in the current window of size ‘N – K’.
Run a loop from 0 to ‘N’.
If i >= N – K then subtract ‘arr[ i – N – K]’ from ‘cur’as this element does not lie in our current window of size ‘N – K’.
Add ‘arr[ i ]’ to ‘cur as this element lies inside our current window of size ‘N – K’.’
If i >= N – K then it shows that we have found a window of size ‘N – K’, So, if ‘minSum’ is greater than ‘cur’ then update ‘minSum’ with ‘cur’.
Return ‘sum’ – ‘minSum’ as this is the maximum score we can make.

Try Problem