Coins in a Line

• Time : $O(n^2)$
• Space : $O(n^2)$

c++

#include <bits/stdc++.h>

int dp[505][505];
int helper(vector<int>& A, int l, int r) {
    if(dp[l][r] != -1) return dp[l][r];
    if(l == r) return dp[l][r] = A[l];
    return dp[l][r] = max(A[l] - helper(A,l+1,r), A[r] - helper(A,l,r-1));
}
int Solution::maxcoin(vector<int> &A) {
    memset(dp,-1,sizeof dp);
    int gap = helper(A,0,A.size() - 1), sum = accumulate(begin(A), end(A), 0);
    return (sum - gap) / 2 + gap;
}