 # 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 … 