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.

解题方法

brute force

两个loop遍历所有subarray, O(n^2)

dp

• 因为最大值有可能由前一个的最大值/最小值 * 当前值得到，所以要有两个array来 保存每个Index的最大值和最小值
• 并且要与当前值比较，有可能只保留当前值

Solution

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)

        minDP = [sys.maxint for i in range(length)]
        maxDP = [sys.maxint for i in range(length)]

        minDP[0] = nums[0]
        maxDP[0] = nums[0]
        maxProduct = nums[0]

        for i in range(1, length):
            minDP[i] = min(min(minDP[i-1] * nums[i], maxDP[i-1] * nums[i]), nums[i])
            maxDP[i] = max(max(minDP[i-1] * nums[i], maxDP[i-1] * nums[i]), nums[i])
            maxProduct = maxDP[i] if maxDP[i] > maxProduct else maxProduct

        return maxProduct

Reference