Consider the following card game between two players. The dealer deals n cards face up in a row. Each card has a value visible to both players. The players move in sequence. Each player, at her turn, can pick either the rightmost or the leftmost of the remaining cards on the table. The game ends when no cards are left. The goal of each player is to accumulate as much value as possible. For example, suppose that n = 5 and the cards have values 3, 2, 1, 7, 4 in order from left to right. Then suppose the players pick the cards in the order 4, 7, 3, 2, 1, where boldface indicates the first players pick, and the remainder the second players pick. Then the first player gets total value 4 + 3 + 1 = 8 and the second gets value 7 + 2 = 9. On the other hand, if the players pick the cards in the order 3, 4, 7, 2, 1, then the first player gets total value 3 + 7 + 1 = 11 and the second gets value 4 + 2 = 6. So, the first player should start by picking the leftmost card with value 3.

Design an O(n^2 ) time algorithm for computing the optimal strategy for the first player. In particular, given a list of values, your algorithm should output whether the first player should pick the leftmost or the rightmost card in order to maximize her total value. Assume that the second player also plays optimally.

return left or right, meaning what card will player one choose at each turn.