Linear time solution


  • 1
    P
        public boolean PredictTheWinner(int[] nums) {
            int N = nums.length;
            if(N % 2 == 0) return true;
            int esum = 0, osum = 0;
            for(int i = 0; i < N; i++) {
                if(i % 2 == 0) esum += nums[i];
                else osum += nums[i];
            }
            int f = Math.max(nums[0], nums[N - 1]);
            esum -= f;
            return f + Math.min(esum, osum) >= Math.max(esum, osum);
        }
    

  • 0
    G
    This post is deleted!

  • 0
    G
    Input:
    [0,0,7,6,5,6,1]
    Output:
    true
    Expected:
    false
    

    But could you explain your solution?

    Upd: I suppose this solution was inspired by the comment
    The mistake is that choosing even or odd elements is one of possible strategies, but is not the best. So you have to write

    if(f + Math.min(esum, osum) < Math.max(esum, osum))
         return false;
    else
        ???     
    

Log in to reply
 

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