Re^2: Puzzle: Given an array of integers, find the best sequence of pop / shift...

[tilly]

Your strategy fails with 3 1 2 100 5 4. (a - b = 2 is greater than 4 - 5 = -1, but you want to pop first.)

Update: The reason why you want to pop first is because then the game goes:

1: pop 4
2: shift 3
1: shift 1
2: pop 5
1: pop 100
2: shift 2

and your score is 95. If you shift first then the game goes:

1: shift 3
2: pop 4
1: shift 3
2: shift 1
1: pop 5
2: pop 100
1: shift 2
and your score is 90.


UPDATE 2: I had the scores right but the sequence of moves wrong.  Sorry.