Coin Game Problem Statement

Wong wants to borrow money from Dr. Strange, who insists Wong must win a coin game first. The game involves two players taking turns to remove one coin from either end of a row of coins arranged by Dr. Strange. Each coin has a value, and the player with the highest total value in the end wins. Wong plays first and seeks to win with your help.

Objective

Given an array of integers, ARR, with each integer representing the value of a coin, determine the maximum value Wong can obtain by following these rules:

1. Players alternate turns and may remove one coin from either end of the array.
2. Once a coin is removed, it cannot be replaced.

Example:

Input:

T = 2
N = 3
ARR = [10, 20, 30]
N = 1
ARR = [100]

Output:

40
100

Explanation:

In the first test case: Wong can remove 30, Dr. Strange removes 20, and Wong removes 10. Wong's total is 40, and he wins.

In the second test case: Wong removes the sole coin of value 100 and wins immediately.

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 10^3
• 1 ≤ ARR[i] ≤ 10^7 where 'ARR[i]' denotes the coin value at the ith position in the array.

Note:

The game ends when no coins are left. If the game is a draw, Wong is considered the winner.