Predict the Winner



For approach #4, code is also wrong. use this code with example '1,5,4' it return false, but right ans should be true;
the correct code below:
public boolean PredictTheWinner(int[] nums) {
int[] dp = Arrays.copyOf(nums,nums.length);
for (int s = nums.length; s >= 0; s) {
for (int e = s + 1; e < nums.length; e++) {
int a = nums[s]  dp[e];
int b = nums[e]  dp[e  1];
dp[e] = Math.max(a, b);
}
}
return dp[nums.length  1] >= 0;
}

@wddtsps
Agree!
Would you plz explain more why copy the original array?public boolean PredictTheWinner(int[] nums) { int[] dp = Arrays.copyOf(nums, nums.length); for (int s = nums.length; s >= 0; s) { for (int e = s + 1; e < nums.length; e++) { int a = nums[s]  dp[e]; int b = nums[e]  dp[e  1]; dp[e] = Math.max(a, b); } } return dp[nums.length  1] >= 0; }

@Kara
If don't copy the original array, the calculation is wrong when "e == s + 1" in the approach #4.
Such as the example [1, 5, 4], if s=1 and e=2, then dp[e]=dp[2] = max(50, 40)=5 according to the code, but the right result should be dp[2] = max(54, 45)=1. So the copy is required for approach #3 and #4.

@bharath4 Agree, for my understanding the result is wrong in approach #3. I've tried to simulate the algorithm on paper with the dp table having the row number as starting index and column number as end index of currently considered subproblem. My result was:
0 1 2 3 4
0 1 4 2 6 0
1 5 3 3 3
2 2 2 4
3 4 2
4 6

Use this tutorial. It makes me understand better https://www.geeksforgeeks.org/dynamicprogrammingset31optimalstrategyforagame/