# java recursive self explanatory solution

• ``````public boolean PredictTheWinner(int[] nums) {

if (nums == null || nums.length < 1) {
return false;
}

int totalSum = 0;

for (int i = 0; i < nums.length; i++) {
totalSum += nums[i];
}
int firstPlayerSum = helper(nums, 0, nums.length - 1);
int secondPlayerSum = totalSum - firstPlayerSum;

return firstPlayerSum >= secondPlayerSum;
}

private int helper(int[] nums, int start, int end) {

if (start > end) {
return 0;
}

int first = nums[start] + Math.min(helper(nums, start + 2, end), helper(nums, start + 1, end - 1));
int last = nums[end] + Math.min(helper(nums, start + 1, end - 1), helper(nums, start, end - 2));

return Math.max(first, last);
}``````

• @pramodnegi I like your solution, easier to follow. But during the recursion there are overlapping combinations of start and end, which is a DP problem. So I added the DP part into your solution, and it runs 6ms!

``````public class Solution {

int[][] mem;

public boolean PredictTheWinner(int[] nums) {

if (nums == null || nums.length < 1) {
return false;
}

int totalSum = 0;

for (int i = 0; i < nums.length; i++) {
totalSum += nums[i];
}

mem = new int[nums.length][nums.length];

int firstPlayerSum = helper(nums, 0, nums.length - 1);
int secondPlayerSum = totalSum - firstPlayerSum;

return firstPlayerSum >= secondPlayerSum;
}

private int helper(int[] nums, int start, int end) {

if (start > end) {
return 0;
}

if(mem[start][end]>0)
return mem[start][end];

int first = nums[start] + Math.min(helper(nums, start + 2, end), helper(nums, start + 1, end - 1));
int last = nums[end] + Math.min(helper(nums, start + 1, end - 1), helper(nums, start, end - 2));
mem[start][end] = Math.max(first, last);
return Math.max(first, last);
}
}``````

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