821. Optimal Strategy for a Game (Coin Row)

Coins are in a row. Two players alternate picking from either end. Both play optimally. Return the maximum score Player 1 can achieve.

Input: An integer array.

Output: Integer.

Examples

Example 1

Input: [5,3,7,10]
Output: 15
Explanation: P1 picks 10, P2 picks 7, P1 picks 5 -> 15.

Example 2

Input: [8,15,3,7]
Output: 22
Explanation: P1 picks 7, P2 picks 8, P1 picks 15 -> 22.