Problem

Alice and Bob continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 

Alice and Bob take turns, with Alice starting first.  Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Examples

Example 1:

1
2
3

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Example 2:

1
2

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

Solution

Method 1 - By minimizing the stones returned by Bob

The game involves Alice and Bob playing optimally to collect as many stones as possible from a row of piles. Alice always plays first, and the players take turns. The key constraints are:

  1. Each player can take any number of piles between 1 and 2M, where M is initially set to 1 and adjusts based on the moves.

  2. The goal is to maximize the number of stones collected by Alice.

  3. Prefix Sums:

    • We use prefixSums to quickly calculate the sum of stones from any subarray.
    • prefixSums[i] stores the total number of stones from the start up to the i-th pile.

  4. Memoization Table:

    • memo[i][M] stores the maximum number of stones Alice can collect starting from index i with the parameter M.
    • This avoids recalculating results for the same state multiple times.

  5. Recursive Function:

    • The helper function findMaxStones handles the game logic recursively.
    • It ensures that both players play optimally, and calculates Alice’s maximum possible stones.

This is how recursion will work:

  • The goal is to maximize Alice’s collected stones. For each possible number of piles X Alice can take (from 1 to 2 * M):
    • Calculate the total stones Alice can collect by summing the stones from index i to i + X - 1.
    • Recursively compute the result for the remaining piles starting from index i + X, and adjust M to max(M, X).
    • Deduct the maximum stones Bob can collect in his turn from the total stones Alice can collect.

Video Explanation

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    private  int[] piles;
    private int[] prefixSums;
    private int n;
    private int[][] memo;
    public int stoneGameII(int[] piles) {
        this.piles = piles;
        this.n = piles.length;
        this.memo = new int[n][n + 1];

        // Initialize memo table to -1 indicating uncomputed states
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        // Calculate prefix sums
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + piles[i];
        }
        this.prefixSums = prefixSums;
        return findMaxStones(0, 1);
    }

    private int findMaxStones(int i, int M) {
        if (i >= n) {
            return 0;
        }

        if (memo[i][M] != -1) {
            return memo[i][M];
        }

        int maxStones = 0;
        int total = 0;

        for (int X = 1; X <= 2 * M && i + X <= n; X++) {
             // Using prefix sums to calculate the sum of stones taken by Alice
             int currentStones = prefixSums[i + X] - prefixSums[i];
             int totalStonesRemaining = prefixSums[n] - prefixSums[i + X];
             // The result of the remaining game
             int nextStones = findMaxStones(i + X, Math.max(M, X));
             
             // Alice's optimal stones after Bob's turn
             maxStones = Math.max(maxStones, currentStones + totalStonesRemaining - nextStones);
        }

        memo[i][M] = maxStones;
        return maxStones;
    }
}

Complexity

  • Time: O(n^3)
    • Because at each recursive call, i goes from 0 to n
    • But another parameter is m and in worst case it can go to n/2
    • Then, we are running the inner loop insider function from X = 1 to n in worst case
  • Space: O(n^2) using recursion stack and memo table

Method 2 - By maximizing the difference

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public class Solution {
    private int[] piles;
    private int[] prefixSums;
    private int n;
    private int[][] memo;

    public int stoneGameII(int[] piles) {
        this.piles = piles;
        this.n = piles.length;
        this.memo = new int[n][n + 1];

        // Initialize memo table to Integer.MIN_VALUE indicating uncomputed
        // states
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }

        // Calculate prefix sums
        this.prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + piles[i];
        }

        // Calculate the maximum difference between Alice's and Bob's stones,
        // starting at index 0 with M = 1
        int maxDifference = findMaxDifference(0, 1);

        // Calculate the total stones using the prefix sums
        int totalStones = prefixSums[n];

        // Calculate Alice's stones based on the maximum difference
        int aliceStones = (totalStones + maxDifference) / 2;

        return aliceStones;
    }

    private int findMaxDifference(int i, int M) {
        if (i >= n) {
            return 0;
        }

        if (memo[i][M] != Integer.MIN_VALUE) {
            return memo[i][M];
        }

        int maxDiff = Integer.MIN_VALUE;

        for (int X = 1; X <= 2 * M && i + X <= n; X++) {
            int currentStones = prefixSums[i + X] - prefixSums[i];
            int nextDiff = findMaxDifference(i + X, Math.max(M, X));
            maxDiff = Math.max(maxDiff, currentStones - nextDiff);
        }

        memo[i][M] = maxDiff;
        return maxDiff;
    }

    public static void main(String[] args) {
        Solution game = new Solution();
        int[] piles = {2, 7, 9, 4, 4};
        System.out.println(game.stoneGameII(piles)); // Expected Output: 10
    }
}

Complexity

  • Time: O(n^2), , where n is the number of piles.
    • There are O(n²) unique states for (i, M):
      • i ranges from 0 to n-1 (start index of remaining piles).
      • M ranges from 1 to n (maximum value for M is n).
    • For each state, the inner loop runs at most O(n) times (since X can go up to 2M, but M ≤ n).
    • However, due to memoization, each state is computed only once, so the total number of recursive calls is O(n²).
    • Thus, the overall time complexity is O(n²).
  • Space: O(n^2)
    • The memoization table memo is of size n × (n+1): O(n²).
    • The prefix sum array is O(n).
    • The recursion stack can go up to O(n) in depth.