maximum product subarray

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.

Go here

这道题和Maximum Subarray其实是很类似的。因此，思路也一样。仅仅是针对乘法做了修改。在 Maximum Subarray里面，我们做加法，因此只需取和的最大值，但是在乘法里面，积最大即可以来自两个最大的自然数，也可以是来自两个最小的负数，因此我们需要两组变量，maxHere, minHere, maxSoFar。代码如下：

class :
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums is None or len(nums) == 0:
            return 0
        minHere, maxHere, maxSoFar = 1, 1, -10000000
        for n in nums:
            tempMin = min(n, min(minHere * n, maxHere * n))
            tempMax = max(n, max(minHere * n, maxHere * n))
            minHere = tempMin
            maxHere = tempMax
            maxSoFar = max(maxHere, maxSoFar)
        return maxSoFar

maximum product subarray

近期文章

近期评论

标签

热门

文章归档

分类目录

功能