Consider the following game. There is a sequence c1 ..cn of coins, where each coin ci has value ci.
Then two players take turns picking a coin from the sequence, but can only pick the first or the last coin of the (remaining) sequence. The goal is to collect coins of the largest total value. For this problem, n is even.
Give an efficient algorithm to determine the maximum possible value for the first player (assuming player two plays optimally), and analyze the running time. Solved by dynamic programming