Problem of the day
You and your friend Ninjax are playing a game of coins. Ninjax place the 'N' number of coins in a straight line.
The rule of the game is as follows:
1. Each coin has a value associated with it.
2. It’s a two-player game played against an opponent with alternating turns.
3. At each turn, the player picks either the first or the last coin from the line and permanently removes it.
4. The value associated with the coin picked by the player adds up to the total amount the player wins.
Ninjax is a good friend of yours and asks you to start first.
Your task is to find the maximum amount you can definitely win at the end of this game.
Note:
'N' is always even number.
Ninjax is as smart as you, so he will play so as to maximize the amount he wins.
Example 1:
Let the values associated with four coins be: [9, 5, 21, 7]
Let’s say that initially, you pick 9 and Ninjax picks 7.
Then, you pick 21 and Ninjax picks 5.
So, you win a total amount of (9+21), i.e. 30.
In case you would have picked up 7 initially and Ninjax would have picked 21 (as he plays optimally).
Then, you would pick 9 and Ninjax would choose 5. So, you win a total amount of (7+9), i.e. 16, which is not the maximum you can obtain.
Thus, the maximum amount you can win is 30.
Example 2:
Let the values associated with four coins be: [20, 50, 5, 10]
Let’s say that initially, you pick 10 and Ninjax picks 20.
Then, you pick 50 and Ninjax picks 5.
So, you win a total amount of (10+50), i.e. 60.
In case you would have picked up 20 initially and Ninjax would have picked 50 (as he plays optimally).
Then, you would pick 10 and Ninjax would choose 5. So, you win a total amount of (20+10), i.e. 30, which is not the maximum you can obtain.
Thus, the maximum amount you can win is 60.
The very first line of input contains an integer T denoting the number of test cases.
The first line of every test case contains an integer ‘N’ denoting the number of coins present in the line initially.
The second line of every test case contains ‘N’ space-separated integers denoting the values associated with the coins placed by Ninjax.
Output format:
For each test case, print the required answer in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= 'T' <= 10
2 <= 'N' <= 10 ^ 3
0 <= 'VALUE' <= 10 ^ 5
Where 'T' is the number of test cases, 'N' is the number of coins and 'VALUE' is the amount on each coin.
Time Limit: 1 sec
2
2
7 8
4
5 30 4 1
8
31
For the first test case, you can pick the maximum value between 7 and 8, which is 8. Thus, Ninjax has to pick up 7.
So, you win a total amount of 8.
For the second test case, first, you pick 1, Ninjax picks 5. Then, you pick 30 and Ninjax picks 4, which is the only coin left. So, you win a total amount of (1 + 30) 31.
3
4
0 5 1 7
6
1 2 3 4 5 6
4
5 5 5 5
12
12
10
A simple and intuitive approach could be to try all the possible combinations of coins we can pick, keeping in mind that the other player plays optimally (i.e. always try to win the maximum amount). Finally, we can select the combination which results in the maximum amount.
Algorithm for the above solution is as follows:
→ Int helper(vector<int> ‘COINS’, int ‘I’, int ‘J'):
→ Int optimalStrategyOfGame(vector<int> ‘COINS’, int ‘N'):
O(4 ^ N) per test case where ‘N’ is the number of coins lined up initially.
In the worst case, the helper function calls 4 recursive calls in it, and in the worst case, we will be generating all possible combinations.
The time complexity can be derived from the recurrence relation:
T(N) = T(N-1) + T(N-1) + T(N-1) + T(N-1)
T(N) = 4 * T(N-1)
O(N) per test case where ‘N’ is the number of coins lined up initially.
In the worst case, extra space will be used by the recursion stack as there can be a maximum of N number of recursive calls at a time.