4 ms one-pass C solution; O(1) space


  • 0
    Z

    The algorithm is as follows. We need 3 different variables to track, a localMax (positive value accumulated since last 0 zero-trap and after even number of negative values). A localMin (negative value accumulated). And an overall Max will be updated along the way.

    Whenever we found a 0 in nums, it's a zero trap, which clears localMax and localMin. New accumulation starts on the number after it.

    Whenever we found a positive number in nums, we accumulate both localMin and localMax as usual.

    Whenever we found a negative number, we keeps accumulating but switches localMax <-> localMin.

    int maxProduct(int* nums, int numsS)
    {
      if(numsS <= 0 || !nums) return 0;
      if(numsS == 1)          return *nums;
      /* 3 variable buffers
         1. localMax
         2. localMin
         3. overallMax
      */
      int lMax = (nums[0]>0)?nums[0]:0;
      int lMin = (nums[0]<0)?nums[0]:0;
      int oMax = lMax;
    
      /* printf("n:%d\tlMax:%d\tlMin:%d\toMax:%d\n", nums[0], lMax, lMin, oMax); */
      
      for(int i =1, tmp; i<numsS; i++)
      {
        if(nums[i]>0)
        {
          /* keeps on accumulating; note zero trap before will be carried over */
          lMax = (lMax == 0)? nums[i] : lMax * nums[i];
          lMin *= nums[i];
        }
        else if(nums[i]<0)
        {
          /* switch the local max/min for a neg */
          tmp = lMax;
          lMax = lMin * nums[i];
          lMin = (tmp == 0)?  nums[i]: tmp*nums[i];
        }
        else  /* a zero-trap */
          lMax = lMin = 0;
    
        oMax = (oMax>=lMax)?oMax:lMax;
    
        /* printf("n:%d\tlMax:%d\tlMin:%d\toMax:%d\n", nums[i], lMax, lMin, oMax); */
      }
    
      return oMax;
    }

Log in to reply
 

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