Suppose you have n coins in a row, and the kth coin in the row has the value vk. You play a 2-player game, where each player takes turns removing a single coin: either the first or last coin in a row. For example, suppose we have 5 coins in the row, and the values are v1 = 5,v2 = 10,v3 = 15,v4 = 5,v5 = 10. On your first turn, you could take coin 1, giving you a value of 5, or coin 5, giving you a value of 10. Then, your opponent could take one from either end (either 1,4 or 2,5, depending on your first move). The best you can do is to take coin 5 (+10), your opponent will then take coin 1 (+5), you then take coin 2 (+10), your opponent takes coin 3 (+15), and then you take coin 4 (+5). This leaves you with a value of 25 and your opponent with a value of 20. Required:
Given an arbitrary number of coins n and a list v1...vn of values, give a dynamic programming algorithm to determine the maximum value that you can get in this game, assuming you go first.