Stone Game II

Description

Alice and Bob continue their stone games. There are several piles of stones arranged in a row, where each pile has a positive number of stones given by piles[i].

Players take turns, with Alice going first. On each turn, the current player takes all the stones from the first X remaining piles (from the left), where 1 ≤ X ≤ 2M. After taking X piles, the value of M is updated to M = max(M, X). Initially, M = 1.

The game continues until all stones have been taken. Both players play optimally to maximize their own total.

Return the maximum number of stones Alice can collect when both players play their best strategy.

The key twist compared to the original Stone Game: players can take a variable number of consecutive piles from the front, and the parameter M grows as players take more piles at once. Taking many piles now gives your opponent the ability to take even more next turn — creating a fascinating strategic tension between grabbing stones now versus limiting your opponent's future options.

Examples

Example 1

Input: piles = [2, 7, 9, 4, 4]

Output: 10

Explanation: One optimal sequence of play:

Alice takes 1 pile: [2] → gets 2 stones. M stays max(1,1) = 1.
Bob takes 2 piles: [7, 9] → gets 16 stones. M becomes max(1,2) = 2.
Alice takes 2 piles: [4, 4] → gets 8 stones. No piles left.
Alice total: 2 + 8 = 10, Bob total: 16.

If Alice takes 2 piles initially (2+7=9), Bob can take all 3 remaining (9+4+4=17 since M=2 allows X up to 4). Alice would get only 9. So Alice's optimal play gives her 10.

Example 2

Input: piles = [1, 2, 3, 4, 5, 100]

Output: 104

Explanation: Alice's optimal strategy is to take small amounts early, keeping M low so Bob can't grab the big pile (100) at the end:

Alice takes 1 pile: [1]. M stays 1.
Bob takes 1 pile: [2]. M stays 1.
Alice takes 1 pile: [3]. M stays 1.
Bob takes 2 piles: [4, 5] → gets 9. M becomes 2.
Alice takes 1 pile: [100] → gets 100.
Alice total: 1 + 3 + 100 = 104, Bob total: 2 + 9 = 11.

The key insight: Alice sacrifices early stones to ensure she reaches the valuable pile at the end.

Constraints

1 ≤ piles.length ≤ 100
1 ≤ piles[i] ≤ 10^4

Editorial

Brute Force

Intuition

This is a two-player game where both players play optimally. The most natural approach is to try every possible move at every turn and find the best outcome.

A powerful simplification is the suffix sum trick. Instead of tracking both players' scores separately, define dfs(i, M) as the maximum stones the current player (whoever's turn it is) can collect from piles[i:] with the given M value.

How does this work? When the current player takes X piles, they get those stones. But the opponent then plays optimally on the remaining piles. The total remaining stones are suffix_sum[i]. Whatever the opponent gets (dfs(i+X, max(M,X))), the current player gets the rest:

current_player_gets = suffix_sum[i] - dfs(i + X, max(M, X))

The current player picks X to maximize this value. This beautifully handles turn alternation without tracking whose turn it is — the same function works for both Alice and Bob.

Without memoization, this recursion explores every possible game tree, leading to exponential time. Many states like dfs(3, 2) get recomputed multiple times through different paths.

Step-by-Step Explanation

Let's trace through piles = [2, 7, 9, 4, 4]. Suffix sums: [26, 24, 17, 8, 4, 0].

Step 1: dfs(0, 1) — Alice faces all piles with M=1. She can take X=1 or X=2.

Step 2: Alice tries X=1. Gets suffix[0] - dfs(1, 1) = 26 - dfs(1, 1). We need dfs(1, 1).

Step 3: dfs(1, 1): Bob faces [7,9,4,4] with M=1. X=1 or X=2.

X=1: 24 - dfs(2, 1)
X=2: 24 - dfs(3, 2)

Step 4: dfs(2, 1): Alice faces [9,4,4] with M=1.

X=1: 17 - dfs(3, 1)
X=2: 17 - dfs(4, 2) = 17 - 4 = 13

Step 5: dfs(3, 1): current player faces [4,4] with M=1.

X=1: 8 - dfs(4, 1) = 8 - 4 = 4
X=2: 8 - dfs(5, 2) = 8 - 0 = 8
dfs(3, 1) = max(4, 8) = 8. Take both piles!

Step 6: dfs(2, 1) = max(17-8, 13) = max(9, 13) = 13. Take X=2 (piles 9+4).

Step 7: dfs(3, 2): [4,4] with M=2. Can take X=1..4.

X=1: 8-4=4. X=2: 8-0=8.
dfs(3, 2) = 8. Note: dfs(4, 2) = 4 was already computed at step 4!

Step 8: dfs(1, 1) = max(24-13, 24-8) = max(11, 16) = 16.

Step 9: Alice's X=1: 26-16=10. Now Alice tries X=2: 26-dfs(2,2).

dfs(2, 2) needs dfs(3, 2)=8 (repeated!), dfs(4, 2)=4 (repeated!), dfs(5, 3)=0.
dfs(2, 2) = max(17-8, 17-4, 17-0) = 17. Alice's X=2: 26-17=9.

Step 10: dfs(0, 1) = max(10, 9) = 10. Alice gets 10 stones.

Brute Force — Game Tree with Overlapping Subproblems — Watch the recursion explore the game tree. Notice repeated computations (highlighted) that cause exponential blowup — the same states are solved again and again.

Algorithm

Compute suffix sums: suffix_sum[i] = total stones from index i to end
Define recursive dfs(i, M) returning max stones current player gets from piles[i:]:
- Base case: if i ≥ n, return 0
- For each X from 1 to 2M (while i+X ≤ n):
  - Current player gets: suffix_sum[i] - dfs(i + X, max(M, X))
- Return the maximum over all valid X
Answer is dfs(0, 1) (Alice starts at position 0 with M=1)

Code

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> suffixSum(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = piles[i] + suffixSum[i + 1];
        }
        return dfs(piles, suffixSum, 0, 1, n);
    }

    int dfs(vector<int>& piles, vector<int>& suffixSum,
            int i, int M, int n) {
        if (i >= n) return 0;
        int result = 0;
        for (int X = 1; X <= 2 * M && i + X <= n; X++) {
            result = max(result,
                suffixSum[i] - dfs(piles, suffixSum, i + X, max(M, X), n));
        }
        return result;
    }
};

class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)
        suffix_sum = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = piles[i] + suffix_sum[i + 1]

        def dfs(i: int, M: int) -> int:
            if i >= n:
                return 0
            result = 0
            for X in range(1, 2 * M + 1):
                if i + X > n:
                    break
                result = max(result,
                    suffix_sum[i] - dfs(i + X, max(M, X)))
            return result

        return dfs(0, 1)

class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] suffixSum = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = piles[i] + suffixSum[i + 1];
        }
        return dfs(piles, suffixSum, 0, 1, n);
    }

    private int dfs(int[] piles, int[] suffixSum,
                    int i, int M, int n) {
        if (i >= n) return 0;
        int result = 0;
        for (int X = 1; X <= 2 * M && i + X <= n; X++) {
            result = Math.max(result,
                suffixSum[i] - dfs(piles, suffixSum, i + X, Math.max(M, X), n));
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(2^n) in the worst case

Without memoization, the recursion can branch into up to 2M children at each level. Since M can grow up to n, and the tree depth is up to n, the total number of recursive calls can be exponential. Specifically, the same (i, M) states are recomputed many times through different paths in the game tree.

Space Complexity: O(n)

The recursion stack has depth at most n (since i increases by at least 1 each call). The suffix sum array uses O(n) additional space.

Why This Approach Is Not Efficient

The brute force recursion is exponential because it recomputes overlapping subproblems. For piles of length 5, we already saw 5 redundant computations. For n=100, the number of redundant calls becomes astronomically large.

However, there are only O(n²) unique states: each state is defined by (i, M) where 0 ≤ i ≤ n and 1 ≤ M ≤ n. If we could compute each state exactly once and store the result, we would eliminate all redundancy.

The fix is dynamic programming — either top-down (memoization) or bottom-up (tabulation). By filling a 2D table of size n × n from the end of the array backward, we compute each state in O(n) time (iterating over valid X values), for a total of O(n³) time. This is a massive improvement from exponential to polynomial.

Comparison showing exponential brute force vs O(n³) DP for Stone Game II with n=100

Optimal Approach - Bottom-Up Dynamic Programming with Suffix Sum

Intuition

We convert the recursive solution to an iterative bottom-up approach. The key insight remains the same: dp[i][M] represents the maximum stones the current player can collect from piles[i:] with parameter M.

The recurrence is:

dp[i][M] = max over X in [1, 2M]: suffix_sum[i] - dp[i + X][max(M, X)]

Base case: when i ≥ n, the value is 0 (no piles left).

We fill the table from bottom to top (i from n-1 down to 0) and for each i, compute all M values from 1 to n. This guarantees that when we compute dp[i][M], the values dp[i+X][max(M,X)] (with i+X > i) are already available.

The suffix sum trick is elegant: rather than accumulating stones pile by pile, we use suffix_sum[i] - dp[i+X][max(M,X)]. This says: "of all stones remaining from position i, I get everything EXCEPT what my opponent will optimally collect." This naturally handles the turn-taking without needing a separate player dimension.

The answer is dp[0][1] — Alice's optimal score starting from position 0 with M=1.

Step-by-Step Explanation

Let's fill the DP table for piles = [2, 7, 9, 4, 4]. Suffix sums: [26, 24, 17, 8, 4, 0].

Step 1 — Initialize: Create dp table. All dp[n][M] = 0 (base case: no piles left).

Step 2 — Fill i=4 (one pile: [4]):

dp[4][M] = 4 for all M ≥ 1. With only 1 pile, the current player takes it.

Step 3 — Fill i=3, M=1 (piles [4, 4]):

X=1: suffix[3] - dp[4][max(1,1)] = 8 - 4 = 4
X=2: suffix[3] - dp[5][max(1,2)] = 8 - 0 = 8
dp[3][1] = max(4, 8) = 8. Take both piles.

Step 4 — Fill i=3, M=2 and M=3: Same result: dp[3][2] = dp[3][3] = 8.

Step 5 — Fill i=2, M=1 (piles [9, 4, 4]):

X=1: 17 - dp[3][1] = 17 - 8 = 9
X=2: 17 - dp[4][2] = 17 - 4 = 13
dp[2][1] = max(9, 13) = 13. Take 2 piles (9+4).

Step 6 — Fill i=2, M=2:

X=1: 17 - dp[3][2] = 9. X=2: 17 - dp[4][2] = 13. X=3: 17 - dp[5][3] = 17.
dp[2][2] = max(9, 13, 17) = 17. With M=2, take all 3!

Step 7 — Fill i=1, M=1 (piles [7, 9, 4, 4]):

X=1: 24 - dp[2][1] = 24 - 13 = 11
X=2: 24 - dp[3][2] = 24 - 8 = 16
dp[1][1] = max(11, 16) = 16. Take 2 piles.

Step 8 — Fill i=1, M=2:

X=1: 24-17=7. X=2: 24-8=16. X=3: 24-4=20. X=4: 24-0=24.
dp[1][2] = 24. Take all 4!

Step 9 — Fill i=0, M=1 (all piles):

X=1: 26 - dp[1][1] = 26 - 16 = 10
X=2: 26 - dp[2][2] = 26 - 17 = 9
dp[0][1] = max(10, 9) = 10. Alice takes 1 pile.

Step 10: Answer: dp[0][1] = 10. Each of the ~15 cells was computed exactly once!

Bottom-Up DP — Filling the Table from End to Start — Watch how we fill the dp[i][M] table bottom-up. Each cell is computed once using already-filled cells below it. The suffix sum trick lets us derive the current player's score from the opponent's optimal value.

Algorithm

Compute suffix sums: suffix_sum[i] = piles[i] + piles[i+1] + ... + piles[n-1]
Create a 2D DP table of size (n+1) × (n+1) initialized to 0
Fill the table from i = n-1 down to 0:
- For each M from 1 to n:
  - For each X from 1 to 2M (while i+X ≤ n):
    - dp[i][M] = max(dp[i][M], suffix_sum[i] - dp[i + X][max(M, X)])
Return dp[0][1]

Code

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();

        // Compute suffix sums
        vector<int> suffixSum(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = piles[i] + suffixSum[i + 1];
        }

        // dp[i][M] = max stones current player gets from piles[i:]
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        for (int i = n - 1; i >= 0; i--) {
            for (int M = 1; M <= n; M++) {
                for (int X = 1; X <= 2 * M && i + X <= n; X++) {
                    dp[i][M] = max(dp[i][M],
                        suffixSum[i] - dp[i + X][max(M, X)]);
                }
            }
        }

        return dp[0][1];
    }
};

class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)

        # Compute suffix sums
        suffix_sum = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = piles[i] + suffix_sum[i + 1]

        # dp[i][M] = max stones current player gets from piles[i:]
        dp = [[0] * (n + 1) for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for M in range(1, n + 1):
                for X in range(1, 2 * M + 1):
                    if i + X > n:
                        break
                    dp[i][M] = max(dp[i][M],
                        suffix_sum[i] - dp[i + X][max(M, X)])

        return dp[0][1]

class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;

        // Compute suffix sums
        int[] suffixSum = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = piles[i] + suffixSum[i + 1];
        }

        // dp[i][M] = max stones current player gets from piles[i:]
        int[][] dp = new int[n + 1][n + 1];

        for (int i = n - 1; i >= 0; i--) {
            for (int M = 1; M <= n; M++) {
                for (int X = 1; X <= 2 * M && i + X <= n; X++) {
                    dp[i][M] = Math.max(dp[i][M],
                        suffixSum[i] - dp[i + X][Math.max(M, X)]);
                }
            }
        }

        return dp[0][1];
    }
}

Complexity Analysis

Time Complexity: O(n³)

The DP table has O(n²) states — n possible values for i (0 to n-1) and n possible values for M (1 to n). For each state (i, M), we iterate over X from 1 to 2M, which in the worst case is O(n) iterations. Total: O(n²) states × O(n) work per state = O(n³). With n ≤ 100, this gives at most ~10⁶ operations, well within time limits.

Space Complexity: O(n²)

The 2D DP table requires (n+1) × (n+1) space. The suffix sum array requires O(n) additional space. Overall: O(n²).

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Stone Game II

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Bottom-Up Dynamic Programming with Suffix Sum

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis