We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stone Game V

Number: 1685

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a row of stones where each stone has an associated positive integer value (provided in an array), Alice and Bob play a game. In each round, Alice splits the row into two non-empty parts. Bob then computes the sum of stones for each part and discards the part with the larger sum (if they are equal, Alice chooses which one to discard). Alice’s score increases by the sum of the remaining part. The game continues on the remaining stones until only a single stone is left. The task is to compute the maximum score that Alice can obtain if she plays optimally.

Key Insights

  • The game is solved via dynamic programming (DP) because the decision at each step depends on the outcome of future moves.
  • Precomputed prefix sums are used to quickly calculate the sum of any subarray.
  • Define a state function f(l, r) representing the maximum score Alice can achieve when considering the subarray from index l to r.
  • When splitting the array at position i (where l <= i < r), calculate the left subarray’s sum and compare it with the right subarray’s sum.
  • Depending on the comparison:
    • If left sum < right sum, Bob discards the right segment and the score gained is left sum plus f(l, i).
    • If left sum > right sum, Bob discards the left segment and the score gained is right sum plus f(i+1, r).
    • If equal, Alice can decide, hence the score is left sum plus the maximum of f(l, i) and f(i+1, r).
  • Base case: When the subarray length is one (l == r), no move can be made; hence, the score is zero.
  • Although the naive recursive formulation might be O(n³) in the worst-case, optimizations (such as using binary search or DP table cuts using monotonicity properties) can reduce the average-case complexity.

Space and Time Complexity

Time Complexity: O(n³) in the worst-case with the straightforward recursive DP approach; optimizations can reduce this. Space Complexity: O(n²) due to the storage used for the DP memoization table and O(n) for the prefix sum array.

Solution

We can solve this problem using recursion with memoization. First, precompute a prefix sum array so that any subarray sum can be computed in constant time. Define a function f(l, r) which computes the maximum score Alice can obtain for the segment from index l to r of the stoneValue array. For every possible cut position between l and r, we compute the left and right sums. Depending on whether the left sum is less than, greater than, or equal to the right sum, we recursively compute the corresponding state. The key idea is to simulate Alice’s optimal decisions in each state while caching intermediate results to avoid recomputation. This approach efficiently explores all valid moves and aggregate the optimal answer.

Code Solutions

# Python code for Stone Game V

def stoneGameV(stoneValue):
    n = len(stoneValue)
    # Precompute prefix sums: prefix[i] is the sum of stoneValue[0...i-1]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stoneValue[i]

    # Memo table for DP where dp[l][r] stores result for stoneValue[l...r]
    dp = [[None] * n for _ in range(n)]

    def helper(l, r):
        # Base case: Only one stone remains, so no score can be obtained.
        if l == r:
            return 0
        if dp[l][r] is not None:
            return dp[l][r]
        
        max_score = 0
        # Try every possible split position between l and r (inclusive of left segment end)
        for i in range(l, r):
            # Sum of stones in the left part is computed using prefix-sum array.
            left_sum = prefix[i+1] - prefix[l]
            right_sum = prefix[r+1] - prefix[l] - left_sum

            if left_sum < right_sum:
                # Bob discards the right part; add left_sum to result from left segment.
                score = left_sum + helper(l, i)
            elif left_sum > right_sum:
                # Bob discards the left part; add right_sum to result from right segment.
                score = right_sum + helper(i+1, r)
            else:
                # Left and right are equal; choose the partition that gives the max future score.
                score = left_sum + max(helper(l, i), helper(i+1, r))
            max_score = max(max_score, score)
        dp[l][r] = max_score
        return max_score

    return helper(0, n - 1)

# Example usage:
stoneValue = [6, 2, 3, 4, 5, 5]
print(stoneGameV(stoneValue))  # Expected output: 18
← Back to All Questions