
Asked in LinkedIn
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.
Be the first one to answer
Add answer anonymously...
Top Software Developer Interview Questions Asked at LinkedIn
Q. What are the steps to create a scalable, UI-focused live chat feature for YouTub...read more
Q. Implement the API call and JSON decryption of incoming data for the given projec...read more
Q. Number of Distinct Substrings Problem Statement Given a string WORD containing l...read more
Interview Questions Asked to Software Developer at Other Companies
Top Skill-Based Questions for LinkedIn Software Developer
Algorithms Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Web Development Interview Questions and Answers
250 Questions
Java Interview Questions and Answers
250 Questions
SQL Interview Questions and Answers
250 Questions
Software Development Interview Questions and Answers
250 Questions
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

