1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

Let's say ABCD are the four outermost notes so that AB-----------CD

Pick A if the higher value note out of B and D is higher value than the higher value note out of A and C, otherwise pick D

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.