Here is a game that you play against a friend. You are given a list of numbers. You move first and pick either the first or the last number from the list, which is then removed from the list. Your friend moves next and again picks either the first or the last number from the list that remains. You move alternately in this manner till all the numbers in the list have been picked. Your score at the end of the game is the sum of numbers that you have picked. Your friend is a master of the game and will always play to ensure that your total score is as small as possible. Your aim is to compute your maximum score under these circumstances. For instance, suppose that the sequence of numbers is the following. 2,5,3,3,2,1 In this case, the maximum score you can obtain is 9. To achieve this, you pick 1 in the first round. This forces your opponent to pick one of the 2's. Depending on which 2 he picks, you can either pick 5 in the second round and 3 in the third round or 3 in the second round and 5 in the third round. |