Bag of Tokens - Implementation

Here is the solution:

function bagOfTokensScore(tokens, P)
 sort tokens ascending
 left := 0
 right := length - 1
 score := 0
 maxScore := 0
 while left <= right
 if P >= tokens[left] then
 P := P - tokens[left]
 score := score + 1
 maxScore := max(maxScore, score)
 left := left + 1
 else if score > 0 then
 P := P + tokens[right]
 score := score - 1
 right := right - 1
 else
 break
 return maxScore

Time: $O(n \log n)$. Space: $O(1)$.

Play cheap tokens face-up, expensive tokens face-down. Track max score seen (not final score).