Problem statement

Alice and Bob take turns with a row of stones, 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 may be negative.

Both play optimally to maximise their own score. Return "Alice", "Bob" or "Tie".

Example 1

Input: stoneValue = [1,2,3,7]
Output: Bob
Explanation: Whatever Alice takes, Bob can take the 7.

Example 2

Input: stoneValue = [1,2,3,-9]
Output: Alice
Explanation: Alice takes all three positives and leaves Bob the -9.

Example 3

Input: stoneValue = [1,2,3,6]
Output: Tie

Constraints

• 1 <= stoneValue.length <= 50000
• -1000 <= stoneValue[i] <= 1000

Hints for Stone Game III

1. Hint 1

   Track the score difference (current player minus opponent) rather than two separate scores.

2. Hint 2

   dp[i] = the best difference the player to move can force from position i.

3. Hint 3

   Taking k stones gives sum(i..i+k-1) - dp[i+k], because the roles then swap.

How to solve Stone Game III

In a zero-sum turn game, one number per position is enough: the best achievable difference for whoever moves next. The opponent's optimal play appears as a subtraction.

Approach

1. Let dp[i] be the maximum score difference the mover can achieve from index i, with dp[n] = 0.
2. For k in 1..3, accumulate the take and evaluate take - dp[i + k].
3. Set dp[i] to the maximum of those candidates.
4. Compare dp[0] with zero to name the winner.

Why it works

After the mover takes k stones, the opponent faces position i + k and will themselves force a difference of dp[i+k] — in their favour. Subtracting flips the perspective back, so maximising take - dp[i+k] is exactly optimal play.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Greedily taking the largest immediate sum ignores what it leaves behind.
• Negative values mean you cannot assume taking more is better — sometimes taking one stone is right.
• dp[n] = 0 anchors the recurrence; the loop must run backwards.

Reference solution

Python

from typing import List

def stoneGameIII(stoneValue: List[int]) -> str:
    n = len(stoneValue)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        take = 0
        best = None
        for k in range(3):
            if i + k >= n:
                break
            take += stoneValue[i + k]
            cand = take - dp[i + k + 1]
            if best is None or cand > best:
                best = cand
        dp[i] = best
    if dp[0] > 0:
        return "Alice"
    if dp[0] < 0:
        return "Bob"
    return "Tie"

Java

public static String stoneGameIII(int[] stoneValue) {
    int n = stoneValue.length;
    int[] dp = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        int take = 0;
        int best = Integer.MIN_VALUE;
        for (int k = 0; k < 3 && i + k < n; k++) {
            take += stoneValue[i + k];
            int cand = take - dp[i + k + 1];
            if (cand > best) best = cand;
        }
        dp[i] = best;
    }
    if (dp[0] > 0) return "Alice";
    if (dp[0] < 0) return "Bob";
    return "Tie";
}

C++

string stoneGameIII(vector<int>& stoneValue) {
    int n = (int) stoneValue.size();
    vector<int> dp(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        int take = 0;
        int best = INT_MIN;
        for (int k = 0; k < 3 && i + k < n; k++) {
            take += stoneValue[i + k];
            int cand = take - dp[i + k + 1];
            if (cand > best) best = cand;
        }
        dp[i] = best;
    }
    if (dp[0] > 0) return "Alice";
    if (dp[0] < 0) return "Bob";
    return "Tie";
}

JavaScript

var stoneGameIII = function(stoneValue) {
    const n = stoneValue.length;
    const dp = new Array(n + 1).fill(0);
    for (let i = n - 1; i >= 0; i--) {
        let take = 0;
        let best = -Infinity;
        for (let k = 0; k < 3 && i + k < n; k++) {
            take += stoneValue[i + k];
            const cand = take - dp[i + k + 1];
            if (cand > best) best = cand;
        }
        dp[i] = best;
    }
    if (dp[0] > 0) return "Alice";
    if (dp[0] < 0) return "Bob";
    return "Tie";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard