# Java DP solution with explanation

• We can use dynamic programming. Suppose after several rounds, the remaining array is nums[i], nums[i+1],... nums[j]

• dp[i][j] = the maximum score of player1 on subarray nums[i..j]

Player1 can choose either nums[i] or nums[j]. If nums[i] is chosen, player2 will also make best effort to get dp[i+1][j]. So for the subarray nums[i+1] ... nums[j], player1 can get:

• nums[i + 1] + nums[i + 2] + ... + nums[j] - dp[i+1][j], which is
• sum(nums[i+1] to nums[j]) - dp[i+1][j]

So we need another array sum to do range sum query, I set sum[0] to 0, sum[i] is the sum of all elements in nums before index i. so finally:

• dp[i][j] = max { sum[j+1] - sum[i+1] - dp[i+1][j] + nums[i],
sum[j] - sum[i] - dp[i][j-1] + nums[j]}
``````    public boolean PredictTheWinner(int[] nums) {
if(nums.length <= 2) return true;
int n = nums.length;
int[] sum = new int[n+1];
sum[0] = 0;
for(int i = 1; i <= n; i ++) {
sum[i] = sum[i-1] + nums[i-1];
}

int[][] dp = new int[n][n];
for(int len = 1; len < n; len ++) {
for(int i = 0; i + len < n; i ++) {
int j = i + len;
if(len == 1) dp[i][j] = Math.max(nums[i], nums[j]);
else {
int can1 = sum[j+1] - sum[i+1] - dp[i+1][j] + nums[i];
int can2 = sum[j] - sum[i] - dp[i][j-1] + nums[j];
dp[i][j] = Math.max(can1, can2);
}
}
}
return sum[n] - dp[0][n-1] <= dp[0][n-1];
}

``````

• @rvanga Hi, thanks for the suggestion. I added some explanation, hope it helps.

• Hi,I think you can use this to make it clearer.

``````  int can1 = sum[j+1] - sum[i] - dp[i+1][j];
int can2 = sum[j+1] - sum[i] - dp[i][j-1];
``````

Because sum[j+1] - sum[i] is the sum of the rest elements, since dp[i+1][j] and dp[i][j-1] is two choices that player 2 can make, the larger one between (sum[j+1] - sum[i] - dp[i+1][j]) and (sum[j+1] - sum[i] - dp[i][j-1]) is the best move player 1 can take.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.