In a recent exam, I've been asked to solve the following problem:
The problem
Two players play the following game: Given a sequence of coin values $v_1,\ldots,v_n (n \vert 2)$ the players take turns in taking one coin from either "end" of the sequence. The value of that coin is added to their score.
Player 1 always starts. What is the maximum score that Player 1 can reach if Player 2 plays optimally (always minimizing their potential score)? What is the time-complexity of your algorithm? Prove your result.
Example:
Given the coin sequence $1,1,3,1,1,2$ one of the best playing sequence for player 1 is (scores denoted as the second tuple):
$$(\lbrack 1,1,3,1,1\rbrack,(2,0)) \rightarrow (\lbrack 1,1,3,1\rbrack,(2,1)) \rightarrow (\lbrack 1,3,1\rbrack,(3,1)) \rightarrow (\lbrack 3,1\rbrack, (3,2)) \rightarrow (\lbrack 1 \rbrack, (6,2)) \rightarrow (6,3)$$
The best score player 1 can reach is 6.
My solution
I'm just going to roughly outline my proof here, the formal correctness is not the point of this question. I'm more interested in the correctness of my asserted upper bound of complexity.
For the following I will use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\ldots,v_j$.
We iteratively create a DAG $G = (V, E, \gamma)$ as follows:
Create a vertex $v$ named $(1,n)$. Create or refer to the previously created vertices $v_1, v_2, v_3$, named $(2,n-1), (3,n), (1,n-2)$ respectively.
Create the edges $e_1 = (v,v_1), \gamma(e_1) = v_1$ and $e_2 = (v,v_2), \gamma(e_2) = max\lbrace v_1, v_n \rbrace$ and $e_3 = (v,v_3), \gamma(e_3) = v_n$. Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$ using a queue or similar to repeat the process until the sequence of coins denoted by the $v$ we iterate over is empty.
The number of edges in the created graph is bounded as follows: $\lvert E \rvert \leq 3\lvert V \rvert$.
The number of vertices is denoted by the following sum: $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$
We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.
This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps
The problem I have with my answer is the upper bound for the number of vertices. I just pull that number out of thin air and my gut-feeling tells me that it is correct, but I might just be completely wrong.
Assuming that this is indeed a correct way to calculate the answer to the question, is my time-complexity argumentation sound?