Optimal Strategy for a Coin Game
You are playing a coin game with your friend Ninjax. There are N
coins placed in a straight line.
Here are the rules of the game:
1. Each coin has a value associated with it.
2. The game involves two players taking alternate turns.
3. On your turn, you may choose a coin from either end of the line and remove it.
4. The value of the coin you remove is added to your total winnings.
Ninjax, being a good friend, lets you begin the game. Determine the maximum amount you can accumulate in the game if both you and Ninjax play optimally.
Input:
The first line contains an integer T
, the number of test cases.
Each test case begins with an integer N
(always even), the number of coins.
The second line consists of N
space-separated integers representing the values of the coins.
Output:
For each test case, output the maximum amount you can definitely win.
Example:
Input:
2
4
9 5 21 7
4
20 50 5 10
Output:
30
60
Explanation:
In the first test case, choosing optimally yields you a total of 30.
In the second test case, choosing optimally yields you a total of 60.
Constraints:
1 <= T <= 10
2 <= N <= 103
0 <= VALUE <= 105
Note: You do not need to handle input or output directly. Implement the solution logic only.
The problem involves finding the optimal strategy to accumulate the maximum amount in a coin game with specific rules.
Start by considering the base cases where there are only 1 or 2 coins.
Use dynamic ...read more
Top Salesforce Member Technical Staff interview questions & answers
Popular interview questions of Member Technical Staff
Top HR questions asked in Salesforce Member Technical Staff
Reviews
Interviews
Salaries
Users/Month