LeetCode 1563 - Stone Game V

In this game, we are given an array stoneValue where each element represents the value of a stone. The stones are arranged in a row, and Alice repeatedly splits the current row into two non-empty contiguous parts.

leetcodehardarraymathdynamic-programminggame-theory

LeetCode Problem 1563

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Game Theory

Solution

Problem Understanding

In this game, we are given an array stoneValue where each element represents the value of a stone. The stones are arranged in a row, and Alice repeatedly splits the current row into two non-empty contiguous parts.

After Alice chooses a split point, Bob compares the sums of the left and right parts:

  • If one side has a larger sum, Bob discards the larger-sum side.
  • Alice gains points equal to the sum of the remaining side.
  • If both sides have equal sums, Alice may choose which side remains.

The game continues recursively on the remaining subarray until only one stone is left. Since a single stone cannot be split further, the game ends at that point.

The objective is to compute the maximum total score Alice can obtain if she plays optimally.

The input is an integer array stoneValue, and the output is a single integer representing the best achievable score.

The constraints are important:

  • 1 <= n <= 500
  • 1 <= stoneValue[i] <= 10^6

The relatively small value of n suggests that dynamic programming over intervals is feasible. However, naive recursion over every possible split can still become extremely expensive because each subarray may branch into many recursive states.

Several edge cases are important:

  • A single stone produces score 0 because no split is possible.
  • Arrays with all equal values can create many tie situations where Alice chooses the better continuation.
  • Highly unbalanced arrays may force Bob to discard large sections repeatedly.
  • Large values require careful handling of sums, but standard 64-bit integers are sufficient.

Approaches

Brute Force Approach

The most direct solution is recursive simulation.

For every subarray [l, r], we try every possible split point k:

  • Left part is [l, k]
  • Right part is [k+1, r]

We compute both sums:

  • leftSum
  • rightSum

Then we follow the rules:

  • If leftSum < rightSum, Alice keeps the left side and gains leftSum.
  • If rightSum < leftSum, Alice keeps the right side and gains rightSum.
  • If equal, Alice chooses the better recursive option.

The recursion explores all possible future decisions and returns the maximum achievable score.

This approach is correct because it explicitly evaluates every legal game sequence. However, it recomputes the same subproblems repeatedly. Since each interval may be revisited many times, the complexity becomes exponential.

Key Insight for the Optimal Solution

The game naturally forms overlapping subproblems.

The important observation is that the future result depends only on the current interval [l, r]. Therefore, we can define a dynamic programming state:

  • dp[l][r] = maximum score obtainable from subarray stoneValue[l:r+1]

For every interval, we try all split positions and compute the best possible score.

To efficiently compute subarray sums, we use prefix sums:

$$\text{sum}(l,r) = prefix[r+1] - prefix[l]$$

This reduces sum computation from O(n) to O(1).

Since there are O(n^2) intervals and each interval tries O(n) split points, the total complexity becomes O(n^3), which is acceptable for n <= 500.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) recursion stack Recomputes the same intervals repeatedly
Optimal Dynamic Programming O(n^3) O(n^2) Memoizes interval results and uses prefix sums

Algorithm Walkthrough

  1. Create a prefix sum array so subarray sums can be computed in constant time.

If prefix[i] stores the sum of the first i elements, then:

$$\text{sum}(l,r)=prefix[r+1]-prefix[l]$$

This is necessary because every interval examines many split points. 2. Define a recursive DP function solve(left, right).

This function returns the maximum score Alice can achieve from the subarray [left, right]. 3. Handle the base case.

If left == right, only one stone remains, so no further move is possible. Return 0. 4. Try every possible split point.

For each mid between left and right - 1:

  • Left interval is [left, mid]
  • Right interval is [mid + 1, right]
  1. Compute the sums of both sides using prefix sums.

Let:

  • left_sum
  • right_sum
  1. Apply the game rules.

If left_sum < right_sum, Bob discards the right side, so Alice gains:

$$left_sum + solve(left, mid)$$

If right_sum < left_sum, Alice gains:

$$right_sum + solve(mid+1, right)$$

If the sums are equal, Alice chooses the better continuation:

$$left_sum + \max(solve(left, mid), solve(mid+1, right))$$ 7. Take the maximum over all split positions.

This ensures Alice always chooses the optimal split. 8. Memoize results.

Since the same intervals appear repeatedly, caching avoids redundant computation.

Why it works

The DP state fully captures the game state because the remaining playable stones are always a contiguous interval. Every legal move corresponds to choosing one split point inside that interval. By evaluating all splits and recursively solving the resulting remaining interval, the algorithm explores every optimal strategy. Memoization guarantees each interval is solved exactly once.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + stoneValue[i]

        def range_sum(left: int, right: int) -> int:
            return prefix[right + 1] - prefix[left]

        @lru_cache(None)
        def solve(left: int, right: int) -> int:
            if left == right:
                return 0

            best = 0

            for mid in range(left, right):
                left_sum = range_sum(left, mid)
                right_sum = range_sum(mid + 1, right)

                if left_sum < right_sum:
                    best = max(
                        best,
                        left_sum + solve(left, mid)
                    )
                elif right_sum < left_sum:
                    best = max(
                        best,
                        right_sum + solve(mid + 1, right)
                    )
                else:
                    best = max(
                        best,
                        left_sum + max(
                            solve(left, mid),
                            solve(mid + 1, right)
                        )
                    )

            return best

        return solve(0, n - 1)

The implementation begins by constructing a prefix sum array. This allows constant-time retrieval of any interval sum, which is critical because every DP state evaluates many split points.

The range_sum helper computes subarray sums efficiently using the prefix array.

The recursive solve(left, right) function represents the maximum score obtainable from a particular interval. The @lru_cache decorator memoizes results so each interval is computed only once.

Inside the recursion, every valid split position is tested. Depending on the comparison between left and right sums, the code follows the exact game rules. The best achievable score across all splits is stored in best.

Finally, the solution returns the result for the entire array.

Go Solution

package main

func stoneGameV(stoneValue []int) int {
	n := len(stoneValue)

	prefix := make([]int, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + stoneValue[i]
	}

	rangeSum := func(left, right int) int {
		return prefix[right+1] - prefix[left]
	}

	dp := make([][]int, n)
	visited := make([][]bool, n)

	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		visited[i] = make([]bool, n)
	}

	var solve func(int, int) int

	solve = func(left, right int) int {
		if left == right {
			return 0
		}

		if visited[left][right] {
			return dp[left][right]
		}

		visited[left][right] = true

		best := 0

		for mid := left; mid < right; mid++ {
			leftSum := rangeSum(left, mid)
			rightSum := rangeSum(mid+1, right)

			if leftSum < rightSum {
				candidate := leftSum + solve(left, mid)
				if candidate > best {
					best = candidate
				}
			} else if rightSum < leftSum {
				candidate := rightSum + solve(mid+1, right)
				if candidate > best {
					best = candidate
				}
			} else {
				leftOption := solve(left, mid)
				rightOption := solve(mid+1, right)

				if rightOption > leftOption {
					leftOption = rightOption
				}

				candidate := leftSum + leftOption

				if candidate > best {
					best = candidate
				}
			}
		}

		dp[left][right] = best
		return best
	}

	return solve(0, n-1)
}

The Go implementation follows the same logic as the Python version but uses explicit memoization tables instead of decorators.

The visited matrix tracks whether a DP state has already been computed. This avoids ambiguity because a legitimate answer may be 0.

Go slices are used for the DP and prefix arrays. Integer overflow is not an issue because the maximum possible total score fits safely within Go's standard int on LeetCode environments.

Worked Examples

Example 1

Input:

[6,2,3,4,5,5]

Prefix sums:

Index Prefix Sum
0 0
1 6
2 8
3 11
4 15
5 20
6 25

Initial interval: [0,5]

Possible splits:

Split Left Sum Right Sum Kept Side Immediate Score
`[6] [2,3,4,5,5]` 6 19 Left
`[6,2] [3,4,5,5]` 8 17 Left
`[6,2,3] [4,5,5]` 11 14 Left
`[6,2,3,4] [5,5]` 15 10 Right
`[6,2,3,4,5] [5]` 20 5 Right

Best first split is at index 2, gaining 11.

Remaining array:

[6,2,3]

Now split again:

Split Left Sum Right Sum Gain
`[6] [2,3]` 6 5
`[6,2] [3]` 8 3

Choose first split, gain 5.

Total so far:

11 + 5 = 16

Remaining array:

[2,3]

Only split:

Split Left Sum Right Sum Gain
`[2] [3]` 2 3

Final score:

11 + 5 + 2 = 18

Example 2

Input:

[7,7,7,7,7,7,7]

Every balanced split creates equal sums, giving Alice freedom to choose the better recursive path.

The optimal strategy repeatedly splits near the center:

Remaining Array Size Gain
7 21
3 7
2 0

Total:

28

Example 3

Input:

[4]

Only one stone exists, so no split can be made.

DP immediately returns:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) There are O(n^2) intervals and each interval checks O(n) split points
Space O(n^2) DP memoization stores one value per interval

The dominant factor comes from iterating through all split points for every interval. Since there are approximately n^2 / 2 intervals and each interval scans up to n positions, the total runtime becomes cubic. The memoization table requires quadratic space.

Test Cases

sol = Solution()

# Provided examples
assert sol.stoneGameV([6,2,3,4,5,5]) == 18  # standard example
assert sol.stoneGameV([7,7,7,7,7,7,7]) == 28  # many equal splits
assert sol.stoneGameV([4]) == 0  # single stone

# Small arrays
assert sol.stoneGameV([1,2]) == 1  # simple two-element case
assert sol.stoneGameV([2,1]) == 1  # reverse order

# Equal values
assert sol.stoneGameV([1,1,1,1]) == 3  # repeated equal partitions

# Increasing values
assert sol.stoneGameV([1,2,3,4,5]) == 10  # prefers smaller side repeatedly

# Decreasing values
assert sol.stoneGameV([5,4,3,2,1]) == 10  # opposite ordering

# Large middle value
assert sol.stoneGameV([1,100,1]) == 1  # forced discard of large side

# Symmetric structure
assert sol.stoneGameV([3,3,3,3]) == 9  # optimal equal splitting

# Stress-style balanced array
assert sol.stoneGameV([10] * 8) == 50  # repeated equal choices

print("All tests passed!")
Test Why
[6,2,3,4,5,5] Verifies standard recursive decisions
[7,7,7,7,7,7,7] Tests equal-sum branching
[4] Minimum input size
[1,2] Simplest nontrivial split
[2,1] Checks asymmetric ordering
[1,1,1,1] Many equal partitions
[1,2,3,4,5] Increasing sequence
[5,4,3,2,1] Decreasing sequence
[1,100,1] Large imbalance handling
[3,3,3,3] Symmetric recursion
[10]*8 Stress test with repeated ties

Edge Cases

Single Stone

An array containing exactly one stone is the smallest legal input. Since the rules require splitting into two non-empty parts, no move can be made. A buggy implementation might attempt recursion anyway or incorrectly return the stone value itself. The implementation correctly handles this through the base case left == right, returning 0.

Equal Partition Sums

When the left and right sums are equal, Alice may choose either side to continue. This is an important source of bugs because some implementations mistakenly choose only one branch. The solution explicitly evaluates both recursive possibilities and takes the maximum.

Highly Unbalanced Arrays

Arrays such as [1,100,1] can force Bob to discard nearly the entire array after a split. Incorrect implementations may accidentally recurse into the discarded side. The algorithm carefully follows the rules and only recurses into the smaller-sum side.

Large Values

Each stone value may be as large as 10^6, and there may be 500 stones. The total sum can therefore become large. Using prefix sums with integer arithmetic avoids repeated recomputation and safely handles large totals within normal integer ranges.