Let there be a line of tokens $t_1, t_2, ..., t_n$ with an integer value $t_i$ between 1 and 1000.
Each turn, I get to pick whether I take the token at the start or at the end of the line, then my opponent gets to do the same. At the end, the player with the highest sum of token values wins.
Now I want to know the maximum guaranteed amount I win if I play optimally, regardless of how my opponent plays. I always have the first turn of the game.
Toy examples:
For a line 4, 1, 3 optimal play would be me taking 4, then my opponent takes either 1 or 3. Let's say they play optimally as well and take 3, then I get 1 for a maximum guaranteed amount of 5.
So that's just a greedy approach and it works.
But for a line 2, 4, 8, 4 a greedy approach isn't optimal.
If I take the 4 at the end, my opponent gets the 8. So in this case, I take the 2, then my opponent has to take either of the two remaining 4s, letting me take the 8 and win the game. The maximum guaranteed amount here is 10.
Some base cases seem to be:
- $n = 1:$ Take $t_1$
- $n = 2:$ Take $\max(t_1, t_2)$
- $n = 3:$ Take $\max(t_1 + \min(t_2, t_3), t_3 + \min(t_1, t_2))$
But then you also have to differentiate in each round whether the current number of remaining tokens is even or odd, and whether the initial $n$ was even or odd.
If $n$ is even, we always get to pick a token in even rounds and the opponent does in odd rounds. If $n$ is odd, it's the other way around.
So if $n$ is even and we're down to three tokens $t_i, ..., t_{i+2}$, it's currently the opponents round so that we would get to add $\min(t_i + \max(t_{i+1}, t_{i+2}), t_{i+2} + \max(t_i, t_i+1))$ to our sum so far, assuming optimal play on the part of the opponent.
I cannot seem to generalise this well enough and I don't know how to think about it in a principled way for arbitrary $n.$ There must be some recursion that I'm just not getting right. Any ideas?
Let $dp_{i,j}$ for all $1\le i\le j \le n$ be defined as the maximum amount you can get in the game where the starting line of tokens is $\{t_i, t_{i+1},\dots t_j\}$. Then it can be defined with this simple recursion as $$ dp_{i,j} = \left\{\begin{align}t_i &&\text{if }i=j \\ \max(t_i+ \left(\sum_{k=i+1}^j t_k\right) - dp_{i+1,j}, t_j+\left(\sum_{k=i}^{j-1} t_k\right) - dp_{i,j-1}) && \text{else} \end{align}\right.$$
This can be viewed as two choices of picking the first $t_i$ and the last $t_j$ token of the line, and then the maximum you can get of the rest of the line is (the sum of tokens - the maximum your opponent can get). It can be simplified as $$ dp_{i,j} = \left\{\begin{align}t_i &&\text{if }i=j \\ \left(\sum_{k=i}^{j} t_k\right) - \min(dp_{i+1,j}, dp_{i,j-1}) && \text{else} \end{align}\right.$$
Then the maximum you can get in the starting line $\{t_1, t_2 \dots t_n\}$ is just $dp_{1,n}$.