1406. Stone Game III

Practice Stone Game III for free on NudgeCode: Hard, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Stones sit in a row with values stoneValue. Alice and Bob alternate turns, Alice first. On a turn a player takes 1, 2 or 3 stones from the front of the row and adds their values to their score. Values can be negative. The game ends when the row is empty. If both play to maximize their own final score, return "Alice" if Alice ends with more, "Bob" if Bob does, or "Tie".

Example

stoneValue = [1,2,3,7]    ->  "Bob"
stoneValue = [1,2,3,-9]   ->  "Alice"
stoneValue = [1,2,3,6]    ->  "Tie"

Constraints