Optimal End-Picking Score

You are given an array values, which may contain negative numbers. Two players take turns removing one number from either end of the array, and each player keeps the sum of the numbers they remove. The first player moves first, and the game ends when the array is empty. Both players play optimally to maximize their own total.

Return the first player's final total.

Examples

Example 1

Input: values = [4,5,1,3]
Output: 8
Explanation: The first player takes the rightmost value 3, leaving [4, 5, 1]. The second player takes 4, leaving [5, 1]. The first player takes 5, and the second player takes the last value 1. The first player's total is 3 + 5 = 8, which is optimal for both sides.

Example 2

Input: values = [-5]
Output: -5
Explanation: The first player must take the only number.