Maximize the Gold

Moderate
0/80
3 upvotes
Asked in companies
Goldman SachsD.E.Shaw

Problem statement

Ninja and his friend have found a hidden treasure. The treasure has ‘N’ bags and each bag has some gold coins in it. Ninja thought of an interesting game, both players will play alternatively. In each turn, the player will choose to pick either the first sack or the last sack and the picked sack of gold will be removed from the treasure. The ninja will start the game and wants to collect the maximum coins possible. Both players will play optimally. Can you help Ninja to find the maximum amount of coins?

You are given an array ‘COINS’ having ‘N’ integers corresponding to the number of coins in each sack. Your task is to find the maximum amount Ninja can collect by playing this game.

For Example 
If the given ‘COINS’ array is [9,6,1,10], then Ninja will collect 10 and 6(Total: 16) and his friend will collect 9 and 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer,' N’ denoting the number of sacks in the treasure.

The next line of each test case has ‘N’ values of ‘COINS’.
Output Format: 
For each test case, return an integer corresponding to the maximum coins  Ninja can collect.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1000.
1 <= COINS[i] <= 1000

Time limit: 1 sec
Sample Input 1:
2
4
9 6 1 10
4
5 2 8 6
Sample Output 1:
16
13
Explanation of sample input 1:
For the first test case,
Ninja will pick the sacks having 10 and 6 coins. So the amount of maximum coins is 16.
Hence the answer is 13.

For the second test case:
Ninja will pick 5 coins in his first turn and 8 in his second turn. So the amount of maximum coins is 13.
Hence the answer is 13.
Sample Input 2:
2
7
8 3 10 3 2 8 1  
5
2 1 3 4 1
Sample Output 2:
21
6
Hint

Try to divide the problem into subproblems and calculate the maximum coins for smaller subarrays.

Approaches (3)
Recursion

In this approach, we will use a recursive function to formulate the answer. We will define a function 'HELPER'(i, j, ’COINS’) that will find the maximum coins that can be collected for the subarray from COINS[i] to COINS[j].

 

Algorithm:

  • Defining 'HELPER'(i, j, ‘COINS’) function.
    • If i > j,return 0.(All coins are picked up, no coins left.)
    • Set ‘FIRST_PICK’ as the maximum number of coins if Ninja picks the first sack.
    • Set ‘LAST_PICK’ as the maxi mum numbe of coins if Ninja  picks the last sack.
    • Set ‘FIRST_PICK’ as COINS[i] + minimum of HELPER(i+2,j,’COINS’) and HELPER(i+1,j-1,’COINS’).
    • Set ‘LAST_PICK’ as ‘COINS’[j] + minimum of HELPER(i,j-2,’COINS’) and HELPER(i+1,j-1,’COINS’).
    • We are adding the minimum because the opponent will also use the optimal strategy.
    • Return the maximum of ‘FIRST_PICK’ and ‘LAST_PICK’.
  • Set ‘ANS’ as 'HELPER'(0, ‘N’ -1, ‘COINS’).
  • Return ‘ANS’.
Time Complexity

O(4^(N^2)), where ‘N’ is the number of sacks in the treasure.

 

In this approach, in the worst case, we will run the 'HELPER' function for all subarrays and in each call, we are iterating over all elements of the subarray. There are a total of N*(N-1) subarrays and for each subarray, we are making at max 4 more recursive calls. So the total time is 4^(N*(N-1)). Hence the overall time complexity is O(4^(N^2)).

Space Complexity

O( 4^(N^2) ), where ‘N’ is the number of sacks in the treasure.
 

In this approach, in the worst case, we are making N^(N*N) calls of the 'HELPER'() function.I will consume stack memory. Hence the overall space complexity is O(4^(N^2))

Code Solution
(100% EXP penalty)
Maximize the Gold
Full screen
Console