1872. Stone Game VIII

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        long[] prefix = new long[n];
        prefix[0] = stones[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + stones[i];
        }

        // dp represents the best score difference the current player can achieve
        // starting from the state where the "cut" is at index i (i.e., first i+1 stones merged)
        long dp = prefix[n - 1];
        for (int i = n - 2; i >= 1; i--) {
            dp = Math.max(dp, prefix[i] - dp);
        }

        return (int) dp;
    }
}

class Solution:
    def stoneGameVIII(self, stones):
        n = len(stones)

        prefix = [0] * n
        prefix[0] = stones[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + stones[i]

        dp = prefix[n - 1]

        for i in range(n - 2, 0, -1):
            dp = max(dp, prefix[i] - dp)

        return dp

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();

        vector<long long> prefix(n);
        prefix[0] = stones[0];

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + stones[i];
        }

        long long dp = prefix[n - 1];

        for (int i = n - 2; i >= 1; i--) {
            dp = max(dp, prefix[i] - dp);
        }

        return (int)dp;
    }
};

class Solution {
    stoneGameVIII(stones) {
        const n = stones.length;

        const prefix = new Array(n);
        prefix[0] = stones[0];

        for (let i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + stones[i];
        }

        let dp = prefix[n - 1];

        for (let i = n - 2; i >= 1; i--) {
            dp = Math.max(dp, prefix[i] - dp);
        }

        return dp;
    }
}