Easiest solution thanks to tushar roy (NRI)


#1

int n=A.size();
pair<int,int> dp[n][n];
for(int i=0;i<n;i++)
{
dp[i][i].first=A[i];
dp[i][i].second=0;
}
for(int l=1;l<n;l++)
{
for(int i=0;i<n-1;i++)
{
int j=i+l;
if(j<n)
{
if(A[i]+dp[i+1][j].second>=dp[i][j-1].second+A[j])
{
dp[i][j].first=A[i]+dp[i+1][j].second;
dp[i][j].second=dp[i+1][j].first;
}
else
{
dp[i][j].first=dp[i][j-1].second+A[j];
dp[i][j].second=dp[i][j-1].first;
}
}
}
}
return dp[0][n-1].first;