Maximum Product Subarray

Question

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.

Tags

• Array
• Dynamic Programming

Thought

Reference: http://bookshadow.com/weblog/2014/10/15/leetcode-maximum-product-subarray/

Like the previous problem, we still use the dynamic programming here. The only difference is that the the product of two negative integers is a positive integer. Thus, we need to also record the minimum product of the subarray during the dynamic programming process.

Code

class Solution(object):
    def maxProduct(self, A):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = max(A)
        size = len(A)
        positive_max = [0 for x in range(size)]
        negative_min = [0 for x in range(size)]
        if A[0] > 0:
            positive_max[0] = A[0]
        elif A[0] < 0:
            negative_min[0] = A[0]
        for x in range(1, size):
            if A[x] > 0:
                positive_max[x] = max(positive_max[x - 1] * A[x], A[x])
                negative_min[x] = negative_min[x - 1] * A[x]
            elif A[x] < 0:
                positive_max[x] = negative_min[x - 1] * A[x]
                negative_min[x] = min(positive_max[x - 1] * A[x], A[x])
            if positive_max[x] and positive_max[x] > ans:
                ans = positive_max[x]
        return ans