Today we continue discussing the best practice from storage engineering:

A strategy for a game
Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by taking turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
 Let us now take an example.
For a sequence of 8, 15, 3, 7
 we know that the maximum value can be 15 + 7
but the players cannot always be greedy. For example, if player one chooses 8 then opponent chooses 15, player one chooses 7 and the opponent chooses 3. Then there are no players left with the maximum. Instead, let us now consider a strategy where the players minimize the profit for the other where we make a choice which leads to progressively lower total for the opponent. When we take a smaller part of the coin sequence, we have the entirely same problem but on a smaller scale. Let us denote the solution for this subproblem with a function F. Then we can lay out the coins from position i to position j. Now a player going first can collect either
Then we make a recursive solution as maximum of the two choices
 F(i,j) = max(Vi + min(F(i+1, j)) ,
                       Vj + min(F(i, j-1))
At the end of both player turns each, two coins have been eliminated with the globally poor choice going to the opponent and the relatively better choice being retained with us. Since the poor and the better are mutually exclusive and there is incremental progression towards the termination, we can also rewrite the recursion in only our own turns to be politically correct:
F(I,j) = max( Vi + max(F(i+2,j), F(i+1, j-1)),
                      Vj + max(F(i+1, j-1), F(I, j-2)))
The function terminates when there are only two coins left from the entire even set.
 Int GetCoins(List<int> coins, int i, int j)
 {
 int n = coins.count;
 If (i >= j) return 0;
 If (i==j) return coins[i];
3 If (j == i+1) return max(coins[i], coins[j]);
 Return max(coins[i] + max(GetCoins(coins, i+2, j), GetCoins(coins, i+1,j-1)) ,
                       coins[j] + max(GetCoins(coins,i+1, j-1), GetCoins(coins,i,j-2)));
 }
Taking our example of 8, 15, 3, 7
we now have max(8 + outcome of (15,3,7) or 7 + outcome of (8,15, 3)) then we have an outcome.
Similarly, for (15,3,7) we have max (15 +outcome of (3,7) or 7 + outcome of (15,3))
Similarly, for (8,15,3) we have max (8 + outcome of (15,3) or 3 + outcome of (8,15))
We could also use a table to keep track of the choices and progression made.
 int GetBest(List<int> coins)
 {
 int n = coins.count;
 int table[n, n];
 int  i, j, k;
 for ( k = 0; k < n; k++)
 {
    for (i = 0; j = k;  j < n; i++; j++)
   {
      int x = ((i+2) <= j) ? table[i+2, j] : 0;
      int y = ((i+1) <= j-1) ? table[i+1, j-1] : 0;
      int z = (i <= (j-2)) ? table[i, j-2]: 0;
      table[i,j] = max(coins[i] + max(x,y), coins[j]+max(y,z));
   }
 }

return table[0, n-1];
 }

This problem can be modified to picking two coins at the same time
In such case the choices to pick the coins are
1) Two from left
2) Two from right
3) One from left and one from right
The first two cases degenerate to picking a coin with a combined value of the two coins.
The last case merely reduces the size of the original sequence:
Therefore this can be elaborated as :
      Int GetCoins(List<int> coins, int i, int j)
 {
 int n = coins.count;
 If (i >= j) return 0;
 If (i==j) return coins[i];
If (j == i+1) return sum(coins[i], coins[j]);
Var option1 = coins[i] + coins [i+1] + max ( GetCoins(coins, i+4, j),
  GetCoins(coins, i+2, j-2), GetCoins(coins, i+3, j-1));
Var option2 = max ( GetCoins(coins, i+2, j),
  GetCoins(coins, i, j-4), GetCoins(coins, i+1, j-3)) + coins [j-1] + coins [j-2];
Var option3 = coins [i]+  max ( GetCoins(coins, i+3, j),
  GetCoins(coins, i+1, j-3), GetCoins(coins, i+2, j-2)) + coins [j];
 Return max(option1, option2, option3);
 }
Taking our example of 8, 15, 3, 7,
The choices are 23 + 10, 10 +23, and 15+18