This problem can be solved in DP.

Let first outline the DP state:

**dp[i][j] means that for a sub-game in between [i, j] inclusive, the maximum score that Player 1 could get.**

Our final goal is to find out whether Player 1 could score more than half of the total score in the game between [0, n-1], or in other words the dp[0][n-1]. Another thing to notice is that, because Player 1 and Player 2 pick numbers one after each other, this means:

**If dp[i][j] means maximum score Player 1 could get between [i, j] then dp[i-1][j] could mean the maximum score Player 2 could get between [i-1, j], and same thing for dp[i][j-1].**

Another more **important** thing based on the above statement is that:

**The sum[i-1][j] - dp[i-1][j] means the maximum score Player 1 can get between [i-1, j] after he picks nums[i] in between [i, j]. Also the same rule applies to dp[i][j-1].**

Thus we have the following induction rule for this DP solution:

**pickLeft = nums[i] + sum[i-1][j] - dp[i-1][j] //if left number is picked**

**pickRight = nums[j] + sum[i][j-1] - dp[i][j-1] //if right number is picked**

**dp[i][j] = max(pickLeft, pickRight)**

Of course we can treat i == j and i == j-1 as special cases:

dp[i][j] = nums[i] // if i == j

dp[i][j] = max(nums[i], nums[j) // if i == j-1

For space complexity reason the sum[i][j] can be replaced with prefixSum.

sum[i][j] = prefixSum[j] - prefixSum[i-1]

```
bool PredictTheWinner(vector<int>& nums) {
vector<vector<int>> score(nums.size(), vector<int>(nums.size()));
vector<int> prefixSum(nums.size()+1);
prefixSum[0] = 0;
for (int i=0; i<nums.size(); i++) {
prefixSum[i+1] = prefixSum[i] + nums[i];
}
for (int len=1; len<=nums.size(); len++) {
for (int lhs=0; lhs+len-1<nums.size(); lhs++) {
int rhs = lhs + len - 1;
if (lhs == rhs) {
score[lhs][rhs] = nums[lhs];
} else if (lhs == rhs-1) {
score[lhs][rhs] = max(nums[lhs], nums[rhs]);
} else {
int pickLeft = nums[lhs] + prefixSum[rhs+1] - prefixSum[lhs+1] - score[lhs+1][rhs];
int pickRight = nums[rhs] + prefixSum[rhs] - prefixSum[lhs] - score[lhs][rhs-1];
score[lhs][rhs] = max(pickLeft, pickRight);
}
}
}
return score[0][nums.size()-1] >= prefixSum.back()/2 + prefixSum.back()%2;
}
```