Bag of Tokens
You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.
Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways, but not both for the same token:
- Face-up: If your current power is at least
tokens[i], you may playtokeni, losingtokens[i]power and gaining1score. - Face-down: If your current score is at least
1, you may playtokeni, gainingtokens[i]power and losing1score.
Return the maximum possible score you can achieve after playing any number of tokens.
Example 1
Input
tokens = [100], power = 50Output
0Since your score is 0 initially, you cannot play the token face-down, and you also cannot play it face-up because your power is less than tokens[0].
Example 2
Input
tokens = [200,100], power = 150Output
1Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1, which is the maximum score achievable.
Constraints
- 0 <= tokens.length <= 1000
- 0 <= tokens[i], power < 10^4