
Asked in Cisco
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 Data Engineer Interview Questions Asked at Cisco
Q. How would you build a pipeline for a Machine learning project?
Q. How do you measure the performance of a model?
Q. Next Greater Number Problem Statement Given a string S which represents a number...read more
Interview Questions Asked to Data Engineer at Other Companies
Top Skill-Based Questions for Cisco Data Engineer
Big Data Interview Questions and Answers
250 Questions
SQL Interview Questions and Answers
250 Questions
Cloud Computing Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Python Interview Questions and Answers
200 Questions
Spark Interview Questions and Answers
50 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

