C++ 4 ms solution with explaination


  • 1
    H
    int maxProduct(vector<int>& nums) {
        if (0 == nums.size()) return 0;
        if (1 == nums.size()) return nums[0];
        //
        // Take an example as below:
        // ... 0, 2, -6, ... , -5, 3, 0, ...
        // If the count of negative numbers between two zeros are even, using all.
        // If the count of negative numbers between two zeros are odd:
        //   Get rid of one side as below: 'current prod/-12'
        //     (2 * -6) == -12 and (-5 * 3) == -15
        //
        int max = INT_MIN;
        int begin = 0, prod = INT_MIN;
        for (int i = 0, size=nums.size(); i < size; ++i) {
            if (0 == nums[i]) {
                // begin <-> end
                prod = extractMaxProd(nums, begin, i-1, prod); 
                if (prod > max) { max = prod; }
                if (0    > max) { max = 0; } // Include 0
                
                while (++i < size && 0 == nums[i]) { }
                
                prod  = INT_MIN;
                begin = i;
                
                --i; // There is an extra ++ at end of 'for'
            } else {
                if (INT_MIN == prod) { prod = nums[i]; } // First one.
                else { prod *= nums[i]; }
            }
        }
        
        prod = extractMaxProd(nums, begin, nums.size()-1, prod);
        if (prod > max) { max = prod; }
        
        return max;
    }
    
    inline int extractMaxProd(vector<int>& nums, int begin, int end, int prod) {
        if (begin == end || prod > 0) return prod;
        
        // Handle 'prod < 0' situation
        int leftProd = 1;
        for (int j=begin; j<=end; ++j) {
            leftProd *= nums[j];
            if (leftProd < 0) break;
        }
        int rightProd = 1;
        for (int j=end; j>=begin; --j) {
            rightProd *= nums[j];
            if (rightProd < 0) break;
        }
        prod /= (leftProd > rightProd) ? leftProd : rightProd;
        return prod;
    }

Log in to reply
 

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