Alert ! Spoilers ahead. This solution is definitely useful and worth looking at


#1
int move(vector<int> &A,int l,int r,vector<vector<int>> &dp){
    if(l>r){return 0;}
    if(dp[l][r]!=-1)return dp[l][r];
    //value - nextmove as next move will be of other player
    return dp[l][r]=max(A[l]-move(A,l+1,r,dp),A[r]-move(A,l,r-1,dp));
    
}
int Solution::maxcoin(vector<int> &A) {
    int l=0,r=A.size()-1;
    vector<vector<int>> dp(r+1,vector<int>(r+1,-1));
    //this gives me the maximum difference of scores among the two so now i can just apply formulae:
    //total sum = commonsum*2  + diff 
    int diff=move(A,l,r,dp);
    int totalsum=0;
    for(int i=0;i<A.size();i++){
        totalsum+=A[i];
    }
    int commonsum=(totalsum-diff)/2;
    return commonsum+diff;
}

In the above solution , I thought what if we keep on moving from 1 move to another in the optimum way (calculate max possible value not just the max of A[l] and A[r])and subtract it from the previous players max so that we can find the maximum difference : For example in this given test case : 1 2 3 4 if we move we will get the max difference as 2 as player1 max will be 6 and at that time player2 max will be 4. This gives me the idea that if i have this difference then i just have to add it to common sum to get my answer.Happy Coding!!


#2

OH WOW @hav_coder YOUR SOLUTION IS JUST SO SATISFYING, AWESOME SOLUTION , HOW DID YOU GET THAT …:rofl: