Near Hollywoo (no d) in LA lies the Bojack Horseman universe, where there is a celebrity show called Hollywoo stars and Celebrities: what do they know? do they know things? lets find out! presented by Mr. Peanutbutter. In this show, there are exactly n different categories of trivia questions, arranged in a row in front of the players. Each question if answered correctly gives the player some value, denoted v1, . . . , vn for each of the n categories. The values are known to the players. Fortunately for the players, Mr. Peanutbutter knows all the answers to the multiple choice questions, and unconsciously, he is giving them away by raising his ears every time he reads through the correct choice. So we can assume players will always get the questions right and score the associated value points.

Bojack faces Pinky Penguin and they play by alternating turns. In each turn, a player selects either the first or last question category from the row, removes it from the row permanently, and receives the value of the category (since the player will answer correctly). Bojack, being a famous celebrity, has the choice of either starting first, or letting his opponent start answering questions first.

Given the row with the n values v1, . . . , vn, determine whether or not Bojack should go first. That is, compute the maximum possible value Bojack can definitely win if he moves first or second, and pick the best for him. Then, give a reconstruction algorithm that tells Bojack exactly which categories (and in what row) to pick. (Hint: your algorithm needs to be efficient, so brute-force algorithms are excluded. Instead, use dynamic programming.)

Note: Pinky Penguin is as clever as Bojack. Before attempting the exercise, think of the following examples: In the first example, the values are 50, 30, 70, 100. In this case, its better if Bojack goes first because he can score 150, by starting with the question of value 100, then Pinky Penguin will select the question of value 70, and then Bojack will select the question of value 50. In the second example, we have values 80, 150, 30, 70. Bojack here should go first and will get 220: first he picks 70 (and not 80), then Pinky Penguin should select 80, then Bojack selects 150 and so he gets 70+150=220. Notice that the greedy strategy of picking the largest available number is not correct.