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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Stone Game V

Difficulty: Hard

Problem Description

Alice and Bob play a game with stones arranged in a row, each with an associated integer value. Alice divides the stones into two non-empty rows, Bob discards the row with the maximum value, and Alice's score increases by the value of the remaining row. The game continues until only one stone remains. Return the maximum score that Alice can obtain.

Key Insights

  • Alice must strategically divide the stones to maximize her score.
  • The game is essentially a dynamic programming problem where each state depends on previous states.
  • The value of a row can be computed using prefix sums for efficient calculation.
  • Handling ties in row values gives Alice the advantage of choosing which row to discard.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

We can approach this problem using dynamic programming. We will use a 2D DP array where dp[i][j] represents the maximum score Alice can achieve from the subarray of stones from index i to j. We also need a prefix sum array to quickly calculate the sum of any subarray. For each possible division point between i and j, we calculate the scores based on Bob's discard strategy and update the DP table accordingly.

Code Solutions

def stoneGameV(stoneValue):
    n = len(stoneValue)
    if n == 1:
        return 0

    # Prefix sum array
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i]

    # DP array
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):  # length of subarray
        for i in range(n - length + 1):
            j = i + length - 1  # ending index
            for k in range(i, j):  # partitioning point
                left_sum = prefix_sum[k + 1] - prefix_sum[i]
                right_sum = prefix_sum[j + 1] - prefix_sum[k + 1]
                if left_sum > right_sum:
                    dp[i][j] = max(dp[i][j], dp[i][k] + right_sum)
                elif left_sum < right_sum:
                    dp[i][j] = max(dp[i][j], dp[k + 1][j] + left_sum)
                else:
                    dp[i][j] = max(dp[i][j], dp[i][k] + left_sum, dp[k + 1][j] + right_sum)

    return dp[0][n - 1]
← Back to All Questions