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.

Examples

Example 1

Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2

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

Constraints

• n == stones.length
• 2 <= n <= 1000
• 1 <= stones[i] <= 1000

Solution

Method 1 – DP with Prefix Sums (Optimal Play)

Intuition

We use DP to compute the maximum difference Alice can achieve, considering both options (removing left or right stone) at each turn. Prefix sums allow efficient calculation of the sum of remaining stones.

Approach

1. Let dp[l][r] be the maximum score difference Alice can achieve from stones l to r.
2. At each turn, Alice can remove the leftmost or rightmost stone, and the remaining sum is added to her score, but Bob will play optimally next.
3. Use prefix sums to compute the sum of any subarray in O(1).
4. The answer is dp[0][n-1].

Code

C++

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> prefix(n+1, 0);
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i];
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l+len <= n; ++l) {
                int r = l+len-1;
                int sum = prefix[r+1] - prefix[l];
                dp[l][r] = max(sum-stones[l] - dp[l+1][r], sum-stones[r] - dp[l][r-1]);
            }
        }
        return dp[0][n-1];
    }
};

Go

func stoneGameVII(stones []int) int {
    n := len(stones)
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ { prefix[i+1] = prefix[i] + stones[i] }
    dp := make([][]int, n)
    for i := range dp { dp[i] = make([]int, n) }
    for length := 2; length <= n; length++ {
        for l := 0; l+length <= n; l++ {
            r := l+length-1
            sum := prefix[r+1] - prefix[l]
            left := sum-stones[l] - dp[l+1][r]
            right := sum-stones[r] - dp[l][r-1]
            if left > right { dp[l][r] = left } else { dp[l][r] = right }
        }
    }
    return dp[0][n-1]
}

Java

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i];
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l+len <= n; ++l) {
                int r = l+len-1;
                int sum = prefix[r+1] - prefix[l];
                dp[l][r] = Math.max(sum-stones[l] - dp[l+1][r], sum-stones[r] - dp[l][r-1]);
            }
        }
        return dp[0][n-1];
    }
}

Kotlin

class Solution {
    fun stoneGameVII(stones: IntArray): Int {
        val n = stones.size
        val prefix = IntArray(n+1)
        for (i in 0 until n) prefix[i+1] = prefix[i] + stones[i]
        val dp = Array(n) { IntArray(n) }
        for (len in 2..n) {
            for (l in 0..n-len) {
                val r = l+len-1
                val sum = prefix[r+1] - prefix[l]
                dp[l][r] = maxOf(sum-stones[l] - dp[l+1][r], sum-stones[r] - dp[l][r-1])
            }
        }
        return dp[0][n-1]
    }
}

Python

class Solution:
    def stoneGameVII(self, stones: list[int]) -> int:
        n = len(stones)
        prefix = [0]*(n+1)
        for i in range(n): prefix[i+1] = prefix[i] + stones[i]
        dp = [[0]*n for _ in range(n)]
        for length in range(2, n+1):
            for l in range(n-length+1):
                r = l+length-1
                total = prefix[r+1] - prefix[l]
                dp[l][r] = max(total-stones[l] - dp[l+1][r], total-stones[r] - dp[l][r-1])
        return dp[0][n-1]

Rust

impl Solution {
    pub fn stone_game_vii(stones: Vec<i32>) -> i32 {
        let n = stones.len();
        let mut prefix = vec![0; n+1];
        for i in 0..n { prefix[i+1] = prefix[i] + stones[i]; }
        let mut dp = vec![vec![0; n]; n];
        for len in 2..=n {
            for l in 0..=n-len {
                let r = l+len-1;
                let sum = prefix[r+1] - prefix[l];
                dp[l][r] = (sum-stones[l] - dp[l+1][r]).max(sum-stones[r] - dp[l][r-1]);
            }
        }
        dp[0][n-1]
    }
}

TypeScript

class Solution {
    stoneGameVII(stones: number[]): number {
        const n = stones.length;
        const prefix = Array(n+1).fill(0);
        for (let i = 0; i < n; i++) prefix[i+1] = prefix[i] + stones[i];
        const dp = Array.from({length: n}, () => Array(n).fill(0));
        for (let len = 2; len <= n; len++) {
            for (let l = 0; l+len <= n; l++) {
                const r = l+len-1;
                const sum = prefix[r+1] - prefix[l];
                dp[l][r] = Math.max(sum-stones[l] - dp[l+1][r], sum-stones[r] - dp[l][r-1]);
            }
        }
        return dp[0][n-1];
    }
}

Complexity

• ⏰ Time complexity: O(n^2) where n is the number of stones.
• 🧺 Space complexity: O(n^2) for the DP table.