Maximum Product Subarray

Question

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

Example

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

Analysis

• Empty array?
• array that has 0
• all positive, all negative? odd negative? even negative?

Thoughts

shuatiblog yu's garden

乘积的问题在于当有negative number时，最大最小有可能会变化 经过research,每次都记录下最大和最小的值，因为如果是负数，下一次乘以负数时有可能变为最大，最大也可能变为最小

注意点

• 可以用O(n)的空间用两个array,也可以只用O（1）两个variable
• O(1)时，要用temp来计算

Solution

class Solution:
    # @param nums: an integer[]
    # @return: an integer
    def maxProduct(self, nums):
        # write your code here
        if not nums:
            return 0
        currentMin = nums[0]
        currentMax = nums[0]
        maxProduct = nums[0]

        for i in range(1, len(nums)):
            #use temp to store currentMin, otherwise it would be changed in next line
            temp = currentMin
            currentMin = min(currentMin * nums[i], currentMax * nums[i], nums[i])
            currentMax = max(temp * nums[i], currentMax * nums[i], nums[i])
            if maxProduct < currentMax:
                maxProduct = currentMax

        return maxProduct