Stone Game VII - Practice Coding Problems

Stone Game VII - Problem

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row.

The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Input & Output

Example 1 — Basic Game

$ Input: stones = [5,3,1,4,2]

› Output: 6

💡 Note: Alice starts and plays optimally. One optimal sequence: Alice removes 2 (scores 5+3+1+4=13), Bob removes 5 (scores 3+1+4=8), Alice removes 4 (scores 3+1=4), Bob removes 1 (scores 3), Alice takes 3 (scores 0). Alice: 13+4=17, Bob: 8+3=11. Difference: 17-11=6.

Example 2 — Small Array

$ Input: stones = [7,90,5,1,100,10,10,2]

› Output: 122

💡 Note: With optimal play from both players, Alice can achieve a score difference of 122 points.

Example 3 — Minimum Size

$ Input: stones = [3,7]

› Output: 4

💡 Note: Alice can remove 3 (gets score 7) or remove 7 (gets score 3). She chooses to remove 3, then Bob must take 7 (gets score 0). Alice: 7, Bob: 0. Difference: 7-0=7. Wait, let me recalculate: if Alice removes 3, remaining is [7], Bob gets 0 points. If Alice removes 7, remaining is [3], Bob gets 0 points. Alice gets 7 or 3 respectively. So Alice gets max(7,3)=7, difference is 7.

Constraints

n == stones.length
2 ≤ n ≤ 1000
1 ≤ stones[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

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

Game Play

Players alternate removing leftmost or rightmost stones

Scoring

Score equals sum of remaining stones after removal

Output

Maximum score difference Alice can achieve: 6

Key Takeaway

🎯 Key Insight: Each player must consider opponent's optimal response when choosing their move

Asked in

G Google 12 a Amazon 8 f Facebook 6

The key insight is that this is a classic game theory problem where each player tries to optimize their own advantage. The optimal approach uses dynamic programming where dp[i][j] represents the maximum score difference achievable in range [i,j]. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible game sequences recursively
Bottom-up Dynamic Programming	O(n²)	O(n²)	Build optimal solutions iteratively using 2D DP table
Memoized Recursion	O(n²)	O(n²)	Add memoization to avoid recalculating same game states

Recursive Brute Force — Algorithm Steps

Step 1: For current range [left, right], calculate sum of stones in this range
Step 2: Try removing left stone: score = sum - stone[left], recurse on [left+1, right]
Step 3: Try removing right stone: score = sum - stone[right], recurse on [left, right-1]
Step 4: Alice picks move that maximizes (her_score - opponent_future_advantage)

Visualization

Tap to expand

Step-by-Step Walkthrough

Game State

Current range of stones [left, right]

Try Both Moves

Remove left stone OR remove right stone

Recurse

Solve subproblem optimally for opponent

Code -

solution.c — C

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

int* prefixSum;

int max(int a, int b) {
    return a > b ? a : b;
}

int getSum(int left, int right) {
    return prefixSum[right + 1] - prefixSum[left];
}

int solve(int left, int right) {
    if (left == right) {
        return 0;
    }
    
    // Try removing left stone
    int sumAfterLeft = getSum(left + 1, right);
    int scoreLeft = sumAfterLeft - solve(left + 1, right);
    
    // Try removing right stone
    int sumAfterRight = getSum(left, right - 1);
    int scoreRight = sumAfterRight - solve(left, right - 1);
    
    // Current player picks the move that maximizes their advantage
    return max(scoreLeft, scoreRight);
}

int solution(int* stones, int n) {
    prefixSum = (int*)calloc(n + 1, sizeof(int));
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + stones[i];
    }
    
    int result = solve(0, n - 1);
    free(prefixSum);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int stones[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            stones[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(stones, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position has 2 choices, creating exponential recursive tree

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 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