int dp[501][501];

int solve(int i,int j,vector A)

{

if(i+1==j)

return max(A[i],A[j]);

if(i==j)

return A[i];

if(dp[i][j]!=-1)

return dp[i][j];

```
return dp[i][j]=max(A[i]+min(solve(i+2,j,A),solve(i+1,j-1,A)),A[j]+min(solve(i,j-2,A),solve(i+1,j-1,A)));
```

}

int Solution::maxcoin(vector &A) {

memset(dp,-1,sizeof(dp));

return solve(0,A.size()-1,A);

}