Consider the following game. A dealer produces a sequence s1 sn of cards, face up

QUESTION:

Consider the following game. A dealer produces a sequence s1 sn of cards, face up, whereeach card si has a value vi. Then two players take turns picking a card from the sequence, butcan only pick the first or the last card of the (remaining) sequence. The goal is to collect cards oflargest total value. (For example, you can think of the cards as bills of different denominations.)Assume n is even.(a) Show a sequence of cards such that it is not optimal for the first player to start by pickingup the available card of larger value. That is, the natural greedy strategy is suboptimal.(b) Give an O(n2) algorithm to compute an optimal strategy for the first player. Given theinitial sequence, your algorithm should precompute in O(n2) time some information, andthen the first player should be able to make each move optimally in O(1) time by lookingup the precomputed information.