lxi. Coins in a Row

Problem. A row of coins with values; two players alternately take a coin from either end. Maximize your total.

Fact	Result
optimal difference (first minus second)	interval DP $d[i][j]=\max (v_i-d[i+1][j],v_j-d[i][j-1])$, $O(n^2)$
even number of coins	the first player can never lose: take all odd positions or all even positions

long long coinsInRow(const vector<long long>& v) {                              // best (first - second) with optimal play
    int n = sz(v); vector<vector<long long>> d(n, vector<long long>(n));
    for (int i = n - 1; i >= 0; i--) { d[i][i] = v[i]; for (int j = i + 1; j < n; j++) d[i][j] = max(v[i] - d[i + 1][j], v[j] - d[i][j - 1]); }
    return n ? d[0][n - 1] : 0;
}

Proof: the DP and the parity strategy

DP. With coins $i..j$ left, the mover takes an end coin and then faces the opponent’s optimal difference on the remaining interval, so the best difference is the maximum of the two options; an empty interval gives $0$. Parity. With an even count, colour positions alternately. The first player can always take a coin of the colour of their choice: initially the two ends have different colours; after taking one end, both new ends of the remaining interval have the other colour, so the opponent must take that colour, which again exposes one coin of each colour. So the first player can collect exactly all coins of the richer colour, which is at least half. Checked against brute-force recursion, including the never-lose claim.