A dealer produces a sequence s1, . . . , sn of cards, face up, where each card si has value vi. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even. (a) Consider a greedy approach for the first player: always picking up the available card of larger value. Give a sequence of cards such that is not optimal for the first player. Explain what the greedy approach will give you and what a better solution is. (b) GiveanO(n2).Giventheinitialsequence , your algorithm should precompute in O(n2) time some information, and then the first player should be able to make each move optimally in O(1) time by looking up the precomputed information.