Java 10 line solution, DP, space complexity O(N)


  • 0
    public boolean PredictTheWinner(int[] nums) {
        if (nums == null || nums.length <= 0) return true;
        int n = nums.length;
        int[] f = new int[n+1];
        for (int j = n; j >= 0; j--) {
            for (int i = 0; i < j; i++) {
                f[i] = Math.max(nums[i] - f[i+1], nums[i+n-j] - f[i]);
            }
        }
        return f[0] >= 0;
    }

Log in to reply
 

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