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
Select
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
Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits