Pattern : 2 DSA+ 60 MCQS

There are several books in the HackerStudy library. One of the mathematics books describes a problem that a mathematician wants to solve.

Given an array of n integers, the mathematician can make the following move:

Choose an index i (0 ≤ i < length(arr)) and add arr[i] to the score. Discard either the left partition (arr[0], ..., arr[i - 1]) or the right partition (arr[i + 1], arr[length(arr) - 1]). The discarded partition can be empty. The chosen partition becomes the new value of arr for subsequent moves.

Starting with an initial score of 0, return the maximum score achievable after k moves.

Example Consider n = 6, arr = [4, 6, -10, -1, 10, -20], and k = 4

One optimal way the mathematician can perform the moves is as follows.

Select arr[4] (0-based), then the left subarray. Now, score = 10 and arr = [4, 6, -10, -1]. Select arr[0] and the right subarray. Now, score = 10 + 4 = 14 and arr = [6, -10, -1]. Select arr[0] and the right subarray. Now, score = 14 + 6 = 20 and arr = [-10, -1]. Select arr[1] and the right subarray. Now, score = 20 + (-1) = 19 and arr = [].

Thus, the answer is 19.

Function Description

Complete the function getMaximumScore in the editor below.

getMaximumScore has the following parameters:

int arr[n]: the input array int k: the number of moves Returns long_int: the maximum score after k moves.

Input Format For Custom Testing

The first line contains an integer, n, the size of arr.

Each of the next n lines contains an integer, arr[i].

The last line contains an integer, k.

Sample Case 0 Sample Input 0 STDIN FUNCTION

---

7 arr[] size n = 7 -5 arr = [-5, 4, -10, -1, -5, 8, -3] 4 -10 -1 -5 8 -3 3 k = 3 Sample Output 0 11 Explanation

One optimal way the mathematician can perform the moves is:

Select arr[5] (0-based), then the left subarray. Score = 8 and arr = [-5, 4, -10, -1, -5]. Select arr[1] and the right subarray. Score = 12 and arr = [-10, -1, -5]. Select arr[1] and the right subarray. Score = 11 and arr = [-5].

Hence, the maximum possible score is 11.