Last Updated: 1 Oct, 2021
Maximize the Gold
Moderate
Asked in companies
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.
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
Approaches
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’.
In the previous approach, we just used recursion to find the answer for each sub-problem.
Now we will use dynamic programming to formulate the answer. We will define a function 'HELPER'(i, j, ’COINS’, ’DP’) that will find the maximum coins player can achieve for the subarray from ‘COINS’[i] to ‘COINS’[j]. We will also use memoization and store this value in DP[i][j].
Algorithm:
- Defining 'HELPER'(i, j, ‘COINS’, ‘DP’) function.
- If i > j,return 0.(All coins are picked up, no coins left.)
- If the answer for this sub-array is pre-computed, we will use that value.
- If DP[i][j] is not equal to -1.
- Return DP[i][j].
- Set ‘FIRST_PICK’ as the maximum number of coins if Ninja picks the first sack.
- Set ‘LAST_PICK’ as the maximum number 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.
- Set ‘DP[i][j]’ as maximum of ‘FIRST_PICK’ and ‘LAST_PICK’.
- Return DP[i][j].
- Declare a 2-D array ‘DP’ to memoize this DP solution.
- Set each value of ‘DP’ as -1.
- Set ‘ANS’ as 'HELPER'(0, ‘N’ -1, ‘COINS’. ‘DP’).
- Return ‘ANS’.
In this approach, we will make a 2D ‘DP’ array of size N*N .’DP’[i][j] will store the maximum amount of coins the player can collect only using the subarray ‘COINS’[i...j]. To fill this ‘DP’ table we will run a loop for ‘GAP’ from 0 to ‘N’.In one iteration of we will fix the values for DP[i][i + ‘GAP’] for all ‘i’. After filling the ‘DP’ table completely, we will return ‘DP’[0][‘N’-1] , the maximum number of coins that can be picked considering the whole array.
Algorithm:
- Declare a 2-Dimensional array ‘DP’ of size ‘N’ * ’N’.
- For ‘GAP’ in range 0 to ‘N’ -1, do the following:
- For i in range 0 to N- ‘GAP’ -1, do the following:
- We will calculate the value of ‘DP’[i][i+’GAP’].
- Set j as i+’GAP’.
- Declare ‘A’, ‘B’, and ‘C’ as the values of the state that the opponent player will face after the player’s turn.
- If i+2<=j:
- Set ‘A’ as DP[i+2][j].
- Else:
- Set ‘A’ as 0.
- If i+1<=j-1:
- Set ‘B’ as DP[i+1][j-1].
- Else:
- Set ‘B’ as 0.
- If i<=j-2:
- Set ‘C’ as DP[i][j-2].
- Else:
- Set ‘C’ as 0.
- Set ‘FIRST_PICK’ as ‘COINS’[i] + minimum of ‘A’ and ‘B’.
- Set ‘LAST_PICK’ as ‘COINS[j]’ + minimum of ‘B’ and ‘C’.
- Set DP[i][j] as the maximum of ‘FIRST_PICK’ and ‘LAST_PICK’.
- For i in range 0 to N- ‘GAP’ -1, do the following:
- Return DP[0][‘N’-1].
Similar problems