Problem Explanation

This problem is about stone game between Alice and Bob where the goal of Alice is to maximize her score. Stone game involves a row of stones, each having an integer value. In each turn, Alice divides the row into two non-empty sub-rows and Bob calculates the sum of the values of all stones in each row. Bob then throws away the row with the maximum value and the sum of the stones in the remaining row is added to Alice's score. If both rows have equal sum, Bob lets Alice decide which row to throw. Alice's initial score is zero. The task is to return the maximum score that Alice can obtain. The game ends when there is only one stone remaining.

Let's walk through the Example 1 from the problem statement:

We have the stone values as [6,2,3,4,5,5].

• In the first round, Alice can divide the row into two as [6,2,3] and [4,5,5], the sum of left row is 11 and right row is 14. Bob throws away right row as it has the maximum sum, and Alice's score is now 11 (the sum of left row).
• In the second round, Alice can further divide the remaining row as [6] and [2,3]. This time, Bob throws away left row (as it has maximum sum) and Alice's score becomes 16 (previous score 11 + sum of right row 5).
• In the third round, Alice has only one choice, to divide as [2] and [3]. Bob throws away right row and Alice's score becomes 18 (previous score 16 + sum of left row 2). The game ends as only one stone is remaining.

The function should return 18.

Solution Approach

This problem can be solved using the Dynamic Programming approach. We will need a 2D-array dp where dp[i][j] stores the maximum score Alice can obtain from the sub-array stoneValue[i..j]. Additionally, a prefix array is used to keep track of the sum of array elements up to each index to avoid multiple calculations.

For any given sub-array stoneValue[i..j], try all the possible partitions and calculate the sum of left and right sub-arrays. If the left sum is less than the right sum, Bob is going to throw the right sub-array and in such case, the score Alice can obtain is the left sub-array's sum plus the maximum score she can get from playing the rest of the game if she starts with the left sub-array. If the left sum is greater than the right sum, Bob is going to throw the left sub-array and vice versa. If the sums are equal, Alice has the choice to decide which side to throw, and she would choose the one which could give her a higher score. So, calculate the maximum score among all possible partitions and return it as the maximum score Alice can obtain from the array stonesValue[i..j].

Pseudocode

Here is the pseudocode for the solution:

• Initialize dp(matrix of size n x n with all elements as INT_MIN) and prefix arrays.
• For i from 0 to j where j is less than the size of the array, dp[i][j] will be the maximum score that Alice can make if we play on the subarray stoneValue[i..j].
• For p from i to < j, calculate dp[i][j] using dp[i][p] and dp[p+1][j] based on the sum of left and right sub-arrays. This is done in a divide and conquer manner.
• Return dp[0][n-1]

The time complexity of this approach is O(n³), as there are n² subproblems and each takes O(n) time to solve, and the space complexity is O(n²) for storing the DP states.

Python Solution

1
2python
3from typing import List
4
5class Solution:
6    def stoneGameV(self, stoneValue: List[int]) -> int:
7        n = len(stoneValue)
8        prefix = [0] * (n + 1)
9        dp = [[0]*n for _ in range(n)]
10        for i in range(n):
11            prefix[i + 1] = prefix[i] + stoneValue[i]
12        # Loop to calculate dp[i][j]
13        for length in range(1, n):
14            for i in range(n - length):
15                j = i + length
16                for k in range(i, j):
17                    left_sum, right_sum = prefix[k+1] - prefix[i], prefix[j+1] - prefix[k+1]
18                    if left_sum <= right_sum:
19                        dp[i][j] = max(dp[i][j], left_sum + (dp[i][k] if left_sum < right_sum else max(dp[i][k], dp[k+1][j])))
20                    if left_sum >= right_sum:
21                        dp[i][j] = max(dp[i][j], right_sum + (dp[k+1][j] if right_sum < left_sum else max(dp[i][k], dp[k+1][j])))
22        return dp[0][n-1]

Java Solution

1
2java
3public class Solution {
4    public int stoneGameV(int[] stoneValue) {
5        int n = stoneValue.length;
6        int[] prefix = new int[n+1];
7        int[][] dp = new int[n][n];
8        for(int i=0; i<n; i++) {
9            prefix[i+1] = prefix[i] + stoneValue[i];
10        }
11        for(int length=1; length<n; length++) {
12            for(int i=0; i<n-length; i++) {
13                int j = i + length;
14                for(int k=i; k<j; k++) {
15                    int leftSum = prefix[k+1] - prefix[i], rightSum = prefix[j+1] - prefix[k+1];
16                    if(leftSum <= rightSum)
17                        dp[i][j] = Math.max(dp[i][j], leftSum + (leftSum < rightSum ? dp[i][k] : Math.max(dp[i][k], dp[k+1][j])));
18                    if(leftSum >= rightSum)
19                        dp[i][j] = Math.max(dp[i][j], rightSum + (rightSum < leftSum ? dp[k+1][j] : Math.max(dp[i][k], dp[k+1][j])));
20                }
21            }
22        }
23        return dp[0][n-1];
24    }
25}

JavaScript Solution

1
2javascript
3var stoneGameV = function(stoneValue) {
4    const n = stoneValue.length;
5    let prefix = new Array(n + 1).fill(0);
6    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
7    for (let i = 0; i < n; i++) {
8        prefix[i + 1] = prefix[i] + stoneValue[i];
9    }
10    for (let length = 1; length < n; length++) {
11        for (let i = 0; i < n - length; i++) {
12            const j = i + length;
13            for (let k = i; k < j; k++) {
14                const leftSum = prefix[k + 1] - prefix[i];
15                const rightSum = prefix[j + 1] - prefix[k + 1];
16                if (leftSum <= rightSum)
17                    dp[i][j] = Math.max(dp[i][j], leftSum + (leftSum < rightSum ? dp[i][k] : Math.max(dp[i][k], dp[k + 1][j])));
18                if (leftSum >= rightSum)
19                    dp[i][j] = Math.max(dp[i][j], rightSum + (rightSum < leftSum ? dp[k + 1][j] : Math.max(dp[i][k], dp[k + 1][j])));
20            }
21        }
22    }
23    return dp[0][n - 1];
24};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int stoneGameV(vector<int>& stoneValue) {
6        const int n = stoneValue.size();
7        vector<vector<int>> dp(n, vector<int>(n));
8        vector<int> prefix(n+1, 0);
9        for (int i=0; i<n; ++i) { 
10            prefix[i+1] = prefix[i] + stoneValue[i]; 
11        }
12        for (int length=1; length<n; ++length) {
13            for (int i=0; i<n-length; ++i) {
14                const int j = i + length;
15                for (int k=i; k<j; ++k) {
16                    int leftSum = prefix[k+1] - prefix[i], rightSum = prefix[j+1] - prefix[k+1];
17                    if (leftSum <= rightSum)
18                        dp[i][j] = max(dp[i][j], leftSum + ((leftSum < rightSum) ? dp[i][k] : max(dp[i][k], dp[k+1][j])));
19                    if (leftSum >= rightSum)
20                        dp[i][j] = max(dp[i][j], rightSum + ((rightSum < leftSum) ? dp[k+1][j] : max(dp[i][k], dp[k+1][j])));
21                }
22            }
23        }
24        return dp[0][n-1];
25    }
26};

C# Solution

1
2csharp
3public class Solution {
4    public int StoneGameV(int[] stoneValue) {
5        int n = stoneValue.Length;
6        int[] prefix = new int[n+1];
7        int[,] dp = new int[n,n];
8        for(int i=0; i<n; i++) {
9            prefix[i+1] = prefix[i] + stoneValue[i];
10        }
11        for(int length=1; length<n; length++) {
12            for(int i=0; i<n-length; i++) {
13                int j = i + length;
14                for(int k=i; k<j; k++) {
15                    int leftSum = prefix[k+1] - prefix[i], rightSum = prefix[j+1] - prefix[k+1];
16                    if(leftSum <= rightSum)
17                        dp[i,j] = Math.Max(dp[i,j], leftSum + (leftSum < rightSum ? dp[i,k] : Math.Max(dp[i,k], dp[k+1,j])));
18                    if(leftSum >= rightSum)
19                        dp[i,j] = Math.Max(dp[i,j], rightSum + (rightSum < leftSum ? dp[k+1,j] : Math.Max(dp[i,k], dp[k+1,j])));
20                }
21            }
22        }
23        return dp[0,n-1];
24    }
25}

Ruby Solution

1
2ruby
3def stone_game_v(stone_value)
4  n = stone_value.length
5  prefix = Array.new(n + 1, 0)
6  dp = Array.new(n) { Array.new(n, 0) }
7  
8  for i in 0..n - 1
9    prefix[i + 1] = prefix[i] + stone_value[i]
10  end
11
12  for length in 1..n - 1
13    for i in 0..n - length - 1
14      j = i + length
15      for k in i..j - 1
16        left_sum = prefix[k + 1] - prefix[i]
17        right_sum = prefix[j + 1] - prefix[k + 1]
18
19        if left_sum <= right_sum
20          dp[i][j] = [dp[i][j], left_sum + (left_sum < right_sum ? dp[i][k] : [dp[i][k], dp[k + 1][j]].max)].max
21        end
22        if left_sum >= right_sum
23          dp[i][j] = [dp[i][j], right_sum + (right_sum < left_sum ? dp[k + 1][j] : [dp[i][k], dp[k + 1][j]].max)].max
24        end
25      end
26    end
27  end
28  return dp[0][n - 1]
29end

In all the solutions, regardless of the programming language, the time complexity is O(n³) and the space complexity is O(n²) where n is the number of stones. These complexities result from the fact that our dynamic programming approach involves a triple-nested loop that iterates over all possible partitions of the stone array and stores the maximum score for each subarray in a 2-dimensional matrix.

While the time complexity is quite high, dynamic programming is a suitable approach in this case because the stone game problem has both optimal substructure and overlapping subproblems properties. The optimal substructure property is displayed when Alice makes an optimal decision at each stage to maximize her score, and the score of any stage depends on the scores of the sub-stages. The overlapping subproblems property is manifested in the repeated computation of the score from the same subarray of stones, which we eliminate by storing the intermediate results in our matrix. Consequently, while the dynamic programming approach might initially compute slowly, its speed advantage becomes apparent when addressing larger problem sizes.