Use tokens to gain score by spending power wisely, aiming to maximize the final score.
You are given an array of token values and an initial amount of power.
You may perform two kinds of moves any number of times:
- Face up: If you have at least as much power as a token's value, you may spend that power to buy the token and gain 1 score.
- Face down: If you currently have at least 1 score, you may sell one token to regain its value in power and lose 1 score.
Each token can be used at most once, and you may use the tokens in any order. Return the maximum score you can achieve.
The key challenge is deciding when to spend power for score and when to trade score back for power so that the total score ends as large as possible.
Input Format
- An integer array
tokens, wheretokens[i]is the value of the -th token. - An integer
power, the initial amount of power.
Output Format
- Return an integer: the maximum score obtainable after any sequence of valid moves.
Constraints
- Each token can be used at most once.
- A face-up move requires current power to be at least the token value.
- A face-down move requires current score to be at least 1.
- You may stop at any time.
Assumed interview-style constraints:
Example 1
Input
tokens = [100], power = 50
Output
0
Explanation
You cannot buy the only token, and selling is impossible because your score starts at 0.
Example 2
Input
tokens = [100,200,300,400], power = 200
Output
2
Explanation
One optimal sequence is: buy 100 face up (score=1, power=100), sell 400 face down (score=0, power=500), then buy 200 and 300 face up (score=2, power=0).
Show 1 more example
Example 3
Input
tokens = [100,200], power = 150
Output
1
Explanation
Buy 100 face up to reach score 1 and power 50. You cannot buy 200, and selling would not help because there is no better token to unlock.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.