O(n) time O(1) C++ Solution, 4ms


  • 0

    Let's consider all the possible maximum product values end at different indices, the idea is that we can find the maximum value among them and that's the answer we are looking for.

    For example, [-3,2,3,-4], the maximum product value end at index 0 is -3, value at index 1 is 2, and then 6, and 72. To get these values, we need to track the accumulated product and the first negative product. In this case, the first negative product is -3. We keep multiplying values until we find the accumulated product is negative, then we can fix it by dividing the first negative product. Let's see we are looking at index 2, the accumulated product is -24, then we can fix it by dividing -3.

    And 0 always triggers reset for all these values. Accumulated product would be reset to 1, the first negative product to 0.

    int maxProduct(vector<int>& nums) {
        if( nums.empty() ) return 0;
        int ma = nums[0], neg=0, product=1, curVal = ma;
        for( int i=0; i<nums.size(); i++ ) {
            product *= nums[i];
            if( nums[i] < 0 ) {
                if( product > 0 ) curVal = product;
                else {
                    if( neg == 0 ) {
                        curVal = nums[i];
                        neg = product;
                    } else {
                        curVal = product/neg; 
                    }
                }
            } else if( nums[i] == 0 ) {
                curVal = 0;
                neg = 0;
                product = 1;
            } else {
                if( product > 0) curVal = product;
                else curVal = product/neg;
            }
            ma = ma < curVal ? curVal : ma;
        }
        return ma;
    }

Log in to reply
 

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