C++ solution using memoization and prefix sum


#1
int dp[505][505];

int solve(vector<int> &A, int l, int r, int *presum){
    if(dp[l][r]!=-1)return dp[l][r];
    if(l==r){
        dp[l][r] = A[l];
        return dp[l][r];
    }
    dp[l][r] = max(presum[r+1]-presum[l]-solve(A, l+1, r, presum), presum[r+1]-presum[l]-solve(A, l, r-1, presum));
    return dp[l][r];
}

int Solution::maxcoin(vector<int> &A) {
    int n = A.size(), presum[A.size()+1];
    presum[0] = 0;
    for(int i=1; i<=A.size(); i++)
        presum[i] = presum[i-1]+A[i-1];
    memset(dp, -1, sizeof(dp));
    return solve(A, 0, n-1, presum);
}