DP Using O(n) space:


  • 0
    M
    public boolean PredictTheWinner(int[] nums) {
        int[] prev = null;
        for(int i = 0; i < nums.length; i++) {
            int[] cur = new int[i+1];
            cur[i] = nums[i];
            for(int j = i - 1; j > -1; j--)
                cur[j] = Math.max(nums[j] - cur[j+1], nums[i] - prev[j]);
    
            prev = cur;
        }
        return prev[0] >= 0;
    }

Log in to reply
 

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