1690

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        int prefix[n];
        int dp[n][n];
        memset(dp, 0, sizeof dp);

        // Calculate prefix sum.
        prefix[0] = stones[0];
        for(int i=1; i<n; i++)
            prefix[i] = stones[i]+prefix[i-1];

        // Apply mcm logic and get answer for each [start, end] pair.
        for(int length=2; length<=n; length++){
            for(int start=0; start<(n-length+1); start++){
                int end = start+length-1;
                int removeFirst = prefix[end]-prefix[start];
                int removeLast = prefix[end-1]-((start-1)>=0 ? prefix[start-1] : 0);
                dp[start][end] = max(removeFirst-dp[start+1][end], removeLast-dp[start][end-1]);
            }
        }
        return dp[0][n-1];
    }
};