You and your eight$-$year$-$old nephew Elmo decide to play a simple card

game. At the beginning of the game, the cards are dealt face up in a long

row. Each card is worth a different number of points. After all the cards are

dealt, you and Elmo take turns removing either the leftmost or rightmost

card from the row, until all the cards are gone. At each turn, you can decide

which of the two cards to take. The winner of the game is the player that

has collected the most points when the game ends.

Having never taken an algorithms class, Elmo follows the obvious greedy

strategy$-$when it's his turn, Elmo always takes the card with the higher

point value. Your task is to find a strategy that will beat Elmo whenever

possible. $($It might seem mean to beat up on a little kid like this, but Elmo

absolutely hates it when grown$-$ups let him win.$)$

$($a$)$ Prove that you should not also use the greedy strategy. That is$,$ show

that there is a game that you can win, but only if you do not follow the

same greedy strategy as Elmo.

$($b$)$ Describe and analyze an algorithm to determine, given the initial se$-$

quence of cards, the maximum number of points that you can collect

playing against Elmo.