Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array[2,3,-2,4],
the contiguous subarray[2,3]has the largest product =6.

Solution

same logic with Maximum Subarray Sum (which uses two single variables. preSums and result)

here we use 3 variables, maxProd, minProd, and res.

be careful, maxProd and minProd has to be updated with info from last iteration. Thus same time ideally in code

Python

Time: O(n)

space: O(1)

def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        maxProd = nums[0]
        minProd = nums[0]
        res = nums[0]
        for i in range(1, n):
            # here maxProd and minProd have to be updated simultaneously
            # because if you update maxProd first, then when updating minProd, the maxProd from this
            # current iteration will mess up the calculation
            maxProd, minProd = max(maxProd * nums[i], minProd * nums[i], nums[i]), min(maxProd * nums[i], minProd * nums[i], nums[i])
            res = max(maxProd, res)

        return res