Stone Game III

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value given as an integer in the array stoneValue.

Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.

Each player's score is the sum of the values of the stones they have taken. Each player's score is 0 initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score; there could also be a tie. The game continues until all stones have been taken.

Assume Alice and Bob play optimally.

Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they will end the game with the same score.

Example 1
InputstoneValue = [1,2,3,7]
Output"Bob"
Alice will always lose because her best move is to take the first three stones for a score of 6, leaving Bob with 7.
Example 2
InputstoneValue = [1,2,3,-9]
Output"Alice"
Alice must choose all three first stones on the first move to win and leave Bob with a negative score.

Constraints

  • 1 <= stoneValue.length <= 5 * 10^4
  • -1000 <= stoneValue[i] <= 1000

Asked at 2 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate