Alice and Bob worked in a restaurant and received n currency notes in total as tips. Every note has a value (either 1 dollar, 5 dollar or 10 dollar) written on it. The currency notes are arranged from left to right on a table in a fixed but arbitrary sequence. In particular, they are not necessarily sorted according to value. Alice and Bob play the following game to split the tip money. Alice and Bob take turns to play and at each turn, the player chooses either the leftmost currency note or the rightmost currency note and takes it. Bob is greedy and always plays using the following strategy; ”If the rightmost note has value larger than the leftmost, then take the rightmost. Otherwise take the leftmost”. Design an efficient algorithm that determines the plays for Alice such that the tip money Alice gets is maximized. Assume n is even and Alice plays the first turn.
I am not able to think how the bob's turn will be accounted for in Alice's max tip recurrence.