class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int N = nums.size();
if (N % 2 == 0)
return true;
int sum_odd = 0, sum_even = 0;
for (int i = 0; i < N; i++) {
if (i & 1)
sum_even += nums[i];
else
sum_odd += nums[i];
}
if (nums[0] >= abs(sum_even  sum_odd + nums[0])  nums[N  1] >= abs(sum_even  sum_odd + nums[N  1]))
return true;
return false;
}
};
C++ O(N) Solution


This algorithm does not work if the input size is odd.
@brendon4565 said in DP O(n^2) + MIT OCW solution explanation:
Your MIT OCW O(n) solution does not work.
The professor in the video only described a O(n) strategy for solving the problem when the size of the problem was even. And for good reason. If the size of the problem is odd, then the question is harder.
An oddsize problem could be decomposed this way. Either the first player picks a[0] and second player must gain at least a[0] more than the first player in the subproblem s[1...n], or , first player picks a[n] and second player must gain at least a[n] more than the first player in the subproblem s[0..n1]. If in either case the second player cannot achieve this then first player wins.
Important to note is that second player, in both cases, must solve the problem of whether or not it is possible for him to earn at least k points more than the first player. This O(n) strategy to meet/break even is not sufficient. This new problem isn't quite as strict as the optimization problem that the dp algorithm solves, but I do not know of any strategy to solve this otherwise.
[0,0,7,6,5,6,1] is an example of a test case that could fail.