Taking turns Alice and Bob play the following game: Given a sequence of numbers: a1, a2, ..., an each player at her/his turn, takes either the first or last number of the sequence. (So if Alice takes a1 at the first turn, then Bob can take either a2 or an at his turn. If Bob takes an then Alice can take either a2 or an1 and so on) The game ends when there are no numbers left. At the end of the game the score of each player is the sum of the numbers she/he took, minus the sum of the numbers of the opponent. Describe a dynamic programming algorithm that computes the maximal score that the first player can guarantee. Prove the correctness of your algorithm. What is the complexity of the algorithm that you suggest?