hackercupai/hackercup

1In preparation for his final exam, Ethan is doing his fourth programming2assignment: finding the subarray with the maximum sum in an array of integers.3 4Given an array of **N** integers **A1..N**, Ethan's task is to find the5maximum sum of any (possibly empty) contiguous subarray of **A**. Ethan has6implemented an algorithm to solve this problem, described by the following7pseudocode:8 9  * 1\. Set **s** and **m** to both be equal to 0. 10  * 2\. Iterate _i_ upwards from 1 to **N**: 11  * 2a. If **Ai** ≥ 0, increment **s** by **Ai**, otherwise set **s** to be equal to 0. 12  * 2b. If **s** > **m**, set **m** to be equal to **s**. 13  * 3\. Output **m**. 14 15Is there any hope for Ethan? With exasperation, you set out in vain to teach16another lesson.17 18The professor of the class has once again left you with some half-written test19cases. You're given an initial array **B1..M**, such that the absolute value20of each element is at most **K**. You'd like to insert **M** \- 1 more21integers into the array, one between each pair of adjacent elements in the22original array, to construct a new array **A1..N** where **N** = 2**M** \- 1.23Each of the inserted elements must likewise have an absolute value of at most24**K**. You'll then feed the new array **A** into Ethan's algorithm. Your goal25is to maximize the absolute difference between the final array's correct26maximum subarray sum and the output of Ethan's algorithm.27 28### Input29 30Input begins with an integer **T**, the number of test cases. For each test31case, there is first a line containing the space-separated integers **M** and32**K**. Then one more line follows containing the **M** space-separated33integers **B1** through **BM**.34 35### Output36 37For the _i_th test case, output a line containing "Case #_i_: " followed by38the maximum possible absolute difference between the correct maximum subarray39sum and the output of Ethan's algorithm.40 41### Constraints42 431 ≤ **T** ≤ 60  441 ≤ **M** ≤ 50  451 ≤ **K** ≤ 50  46-**K** ≤ **Ai** ≤ **K**   47 48### Explanation of Sample49 50In the first case, **A** = [3], and both Ethan's answer and the correct answer51are equal to 3.52 53In the second case, **A** = [-3], and both Ethan's answer and the correct54answer are equal to 0.55 56In the third case, one value will be inserted into **B**, and you should57choose to insert -1 to yield **A** = [2, -1, 2]. This results in Ethan's58answer being 2 and the correct answer being 3, yielding an absolute answer59difference of 1.60 61In the fourth case, there are multiple choices of inserted elements which62result in an absolute answer difference of 3. For example, it's possible for63Ethan's answer equal to be made to equal 3 while the correct answer equals 6.64 65