Maximize Score

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.

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

Test Case 1 : Given N = 5 and K = 1. arr = [10, 2, 8, 9, 2] Initial score = 0 In the first operation choose 10 from the start and add it to the score. So final score = 10. Test Case 2 : Given N = 5 and K = 2. arr = [10, 5, 6, 7, 9] Initial score = 0 In the first operation choose 10 from the start and add it to the score. So score = 10 and arr = [5, 6, 7, 9] In the second operation choose 9 from the end and add it to the score. So final score = 10 + 9 = 19.

Test Case 1 : Given N = 4 and K = 4. arr = [10, 2, 2, 2] Initial score = 0 Here N = K. So we can add all elements to our score by always picking array elements from the start. So final score = 10 + 2 + 2 + 2 = 16. Test Case 2 : Given N = 4 and K = 3. arr = [10, 1, 7, 9] Initial score = 0 In the first operation choose 10 from the start and add it to the score. So score = 10 and arr = [1, 7, 9] In the second operation choose 9 from the end and add it to the score. So score = 10 + 9 = 19 and and arr = [1, 7] In the third operation choose 7 from the end and add it to the score. So final score = 19 + 7 = 26.

Brute force

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.

Time Complexity

O(N ^ 2), where ‘N’ is the total number of elements in the array.

Calculating ‘sum’ takes O(N) time as we are running a single loop to calculate it. Also, calculating ‘minSum’ takes O(N ^ 2) time as we are running two loops to calculate it. So, the overall time complexity will be O(N ^ 2).

Space Complexity

O(1).

No extra space is being used. Hence, the overall space complexity is O(1).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2: