Taco Game: Optimal Strategy

Alice and Bob are playing a game with an array of integers. In this game, both players take turns picking either the first or the last element from the remaining array, and the player who collects the maximum sum wins. Both players play optimally. Your task is to compute the maximum sum that Alice can achieve if she starts first.

The game can be modeled using dynamic programming with the following recurrence:

$$ \text{dp}[i][j] = \max\Big\{ a[i] + \min\big(\text{dp}[i+2][j],\, \text{dp}[i+1][j-1]\big),\quad a[j] + \min\big(\text{dp}[i+1][j-1],\, \text{dp}[i][j-2]\big) \Big\} $$

Here, \(a\) represents the array of integers and \(\text{dp}[i][j]\) denotes the maximum sum a player can obtain from the subarray \(a[i]\) to \(a[j]\) assuming both players play optimally.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers, which are the values of the array.

outputFormat

Output a single integer — the maximum sum that Alice can achieve if she starts first.

4
1 2 3 4

6