Stone Game V - Practice Coding Problems

Stone Game V - Problem

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away.

The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice's score is initially zero.

Return the maximum score that Alice can obtain.

Input & Output

Example 1 — Basic Game

$ Input: stoneValue = [6,2,3,4,5,5]

› Output: 18

💡 Note: Alice can split at index 2: left=[6,2,3]=11, right=[4,5,5]=14. Bob takes 14, Alice gets 11. Continue with [6,2,3] to get total score 18.

Example 2 — Small Array

$ Input: stoneValue = [7,7,7,7,7,7,7]

› Output: 28

💡 Note: All stones have equal value. Alice can make strategic splits to maximize her remaining portions, achieving a total score of 28.

Example 3 — Minimum Size

$ Input: stoneValue = [4]

› Output: 0

💡 Note: Only one stone remaining, game ends immediately. Alice's score is 0.

Constraints

1 ≤ stoneValue.length ≤ 500
1 ≤ stoneValue[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stone values [6,2,3,4,5,5]

Alice Splits

Alice chooses split point, Bob takes larger sum

Output

Maximum total score Alice can achieve: 18

Key Takeaway

🎯 Key Insight: Alice must think ahead - choose splits that maximize her total score across all future game rounds

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that Alice wants to maximize her total score by choosing splits that give her the best remaining options after Bob's greedy choice. The optimal approach uses dynamic programming to consider all possible game states. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible splits recursively without memoization
Bottom-Up Dynamic Programming	O(n³)	O(n²)	Build solution iteratively from smaller subarrays to larger ones
Memoized Recursion	O(n³)	O(n²)	Cache results of subproblems to avoid recomputation

Recursive Brute Force — Algorithm Steps

For current array, try every split point i
Calculate left sum and right sum
Bob takes larger sum, Alice gets smaller sum
Recursively solve for remaining subarray
Return maximum score across all splits

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Array

Start with full array [6,2,3,4,5,5]

Try Split at Index 2

Left=[6,2,3]=11, Right=[4,5,5]=14, Bob takes 14, Alice gets 11

Recursively Solve

Continue with remaining subarray [6,2,3]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solve(int* stones, int left, int right) {
    if (left >= right) return 0;
    
    int maxScore = 0;
    int total = 0;
    for (int k = left; k <= right; k++) {
        total += stones[k];
    }
    
    for (int i = left; i < right; i++) {
        int leftSum = 0;
        for (int k = left; k <= i; k++) {
            leftSum += stones[k];
        }
        int rightSum = total - leftSum;
        
        int score;
        if (leftSum < rightSum) {
            score = leftSum + solve(stones, left, i);
        } else if (leftSum > rightSum) {
            score = rightSum + solve(stones, i + 1, right);
        } else {
            int leftOption = solve(stones, left, i);
            int rightOption = solve(stones, i + 1, right);
            score = leftSum + (leftOption > rightOption ? leftOption : rightOption);
        }
        
        if (score > maxScore) {
            maxScore = score;
        }
    }
    
    return maxScore;
}

int solution(int* stoneValue, int size) {
    return solve(stoneValue, 0, size - 1);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int stoneValue[500];
    int size = 0;
    
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        stoneValue[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int result = solution(stoneValue, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position can create two recursive calls, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler