Bag of Tokens
Medium · two pointers
In a small arcade game you start with energy units of energy and zero points. In front of you lie some gems. The list gems gives the value of each gem. Every gem can be used at most once, and you may use the gems in any order you like. For each gem you choose one of two moves:
- Buy: if your energy is at least the gem's value, spend that much energy and gain 1 point.
- Sell: if you have at least 1 point, spend 1 point and gain energy equal to the gem's value.
You do not have to use every gem. Return the largest number of points you can hold at any moment during the game.
Examples
Example 1
Input: gems = [100, 200, 300], energy = 200
Output: 1
Buy the 100 gem for 1 point and 100 energy is left. That is not enough for the 200 gem. Selling the point for the 300 gem leaves 0 points, so the best is 1.
Example 2
Input: gems = [100, 200, 300, 400], energy = 200
Output: 2
Buy 100 (1 point, 100 energy left), sell the point for the 400 gem (0 points, 500 energy), then buy 200 and 300 (2 points).
Example 3
Input: gems = [500], energy = 100
Output: 0
Constraints
- 1 <= len(gems) <= 1000
- 0 <= gems[i], energy <= 10^4