Bottom Up, Easy, C++, what more you need, Deepika?


#1

Point is that we have two choices to pick from at every turn. So whatever we choose, opponent will try to minimise the maximum profit we get when he gets to choose.
So we choose the maximum value we get after he plays optimally.

    
int get(vector<vector<int> > &dp , int  i ,int j)
{
    if(i>j) return 0;
    return dp[i][j];
}

int Solution::maxcoin(vector<int> &a) {
    
    int i,j,n,len;
    n = a.size();
    
    vector<vector<int> > maxdp(n , vector<int>(n));
    for(i=0;i<n;i++)
        maxdp[i][i] = a[i];
    
    
    for(len=1;len<n;len++)
    {
        for(i=0;i<n-len;i++)
        {
            j=i+len;
            int x = a[i] + min(get(maxdp , i+2 , j) , get(maxdp , i+1 , j-1));
            int y = a[j] + min(get(maxdp , i+1 , j-1) , get(maxdp , i , j-2));
            

            maxdp[i][j] = max(x,y);
        }
    }
    
    return maxdp[0][n-1];
    
}