# java DP solution with explanation

• If the first player choose nums[0], the max he can get is sum( nums )-max[1, end](which is max for the second player). If the first player choose the last element in nums, then the max he can get is sum(nums)-max[0, end-1](which is the max for the second player). Thus, the DP formula is DP[start][end]=Max(sum-dp[start][end-1], sum-dp[start+1][end]).

One thing I wanna to mention is that, sum in the DP formula is not the total sum for nums, but the sum for nums[start, end].

``````public boolean PredictTheWinner(int[] nums) {
int length = nums.length;

int sum = 0;
for(int num : nums) sum+=num;

int[][] dp = new int[length][length];

for(int j = 0 ; j< length ; j++)
{
int curSum = 0;
for(int i = j ; i>= 0 ; i--)
{
curSum+=nums[i];
if(i == j) dp[i][j]=nums[j];
else
{
dp[i][j]=Math.max(curSum-dp[i][j-1], curSum-dp[i+1][j]);
}
}
}
return dp[0][length-1]*2>=sum;
}
``````

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