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/

The approach#3 is just wrong. For the array mentioned {1, 5, 2, 4, 6}, the first player may pick 6 first, then the second player has to pick 4 or he would lose. Then the first one pick 2, the second picks 5, the first player picks 1, so finally both would be 9, the first one win. Still thanks a lot for your fantastic analysis. The problem is that first you should let dp[i][i] be nums[i], then it works.

@jinzhichengche you are right.this is my solution based on your idea.
class Solution { public boolean PredictTheWinner(int[] nums) { int len = nums.length; int[] dp = new int[len]; for(int i = len  2;i >= 0;i){ dp[i] = nums[i]; for(int j = i + 1;j < len;j++) dp[j] = Math.max(nums[i]  dp[j],nums[j]  dp[j  1]); } return dp[len  1] >= 0; } }