Two players take turns picking 1 to 3 stones from the start of an array. Each stone has a value, and both play optimally to maximize their own total score.
Problem
You are given an array stoneValue, where stoneValue[i] is the value of the -th stone in a row.
Two players, Alice and Bob, take turns. On each turn, a player must take 1, 2, or 3 stones from the front of the remaining row. The stones taken are removed from the row, and the player earns the sum of their values.
Both players play optimally.
Return the result of the game from Alice's perspective:
- `
Input Format
Input
- A single integer array
stoneValue.
Constraints
- The array contains at least one stone.
- Each move must take 1 to 3 stones from the front.
- Assume standard integer values for stone scores.
Output Format
Output
Return one of the following strings:
"Alice"if Alice's final score is greater than Bob's,"Bob"if Bob's final score is greater than Alice's,"Tie"if both scores are equal.
Example 1
Input
stoneValue = [1,2,3,7]
Output
"Bob"
Explanation
Alice can take at most 1, 2, or 3 stones first. With optimal play, Bob can secure a larger total score overall.
Example 2
Input
stoneValue = [1,2,3,-9]
Output
"Alice"
Explanation
Alice can take the first three stones for a total of 6, leaving a negative stone for Bob. That gives Alice the better final score.
Show 1 more example
Example 3
Input
stoneValue = [1,2,3,6]
Output
"Tie"
Explanation
With optimal play, both players can end with the same total score.
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.