# Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming

The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an opponent, alternating turns. In each turn, a player selects either the first or last number, removes it from the row, and collects that much money.

For example, if the numbers are 1,2,3,4 , a possible game may look like:

1. Player A takes 4: row is 1,2,3.
2. Player B takes 3: row is 1,2.
3. Player A takes 1: row is 2.
4. Player B takes 2, game over.

Both players ended with a total amount of 5. Note that A could have done better.

(2 pts) Show an example where the greedy algorithm fails to achieve the highest possible amount of money.

The solution to this problem Greedy Sol used a solution list of number of [1,2,10,3]. However I would argue using the greedy algorithm, " In each turn, a player selects either the first or last" would work here to achieve the highest amount of money. Here is how I would work out the greedy algorithm

1. Player A takes 1: row is 2, 10, 3.
2. Player B takes 3: row is 2, 10.
3. Player A takes 2: row is 10.
4. Player B takes 10, game over.

And Player B has achieved the highest possible amount of money, 13.

Does everyone agree with my walkthrough and that the solution is wrong?

The solution I came up was 2, 8, 7, 6, 4. The idea I had here was that the highest amount of money could only be achieved by the player picking first(3 numbers).

For the player who picks first to achieve the highest possible amount of money. he or she would have to pick 8, 7, and 6. However with this greedy algorithm, that player in the first move either has to choose 2 or 4, meaning the highest possible amount of money is not achievable.(bc player 1 was the only player that could achieve the highest amount of money)

• The greedy algorithm says "take the larger of first or last", so in that example, per the greedy algorithm, $A$ would first take $3$, making $10$ accessible to $B$. Taking either first or last is the rule of the game. – Daniel Fischer May 6 '15 at 19:43
• The point of the solution is that if A uses the greedy algorithm, A will not achieve the optimal payout. Forget about B's strategy and payout. – vadim123 May 6 '15 at 19:44
• @vadim123 Wouldn't you have to consider that A or B could achieve the optimal payout? – committedandroider May 6 '15 at 19:48
• @DanielFischer So Just to make sure with [1, 2, 3, 4], the greedy algorithm will also not achieve the optimal payout? – committedandroider May 6 '15 at 19:50
• For [1,2,3,4], the greedy algorithm works, if $B$ plays well, the $6$ that the greedy algorithm gives $A$ is optimal. – Daniel Fischer May 6 '15 at 19:54