Python solution with detailed explanation


  • 0
    G

    Solution

    Maximum Product Subarray https://leetcode.com/problems/maximum-product-subarray/?tab=Description

    1. https://www.quora.com/How-do-I-solve-maximum-product-subarray-problems
    2. Use an example: [2,-3,4,-8,0]
    3. Insights:
      What if the array has just positive numbers including zero?
      A solution of this will maintain max_prod[i] where max_prod[i] is the maximum subarray product ending at i. Then max_prod[i+1] = max(max_prod[i] * nums[i+1], nums[i+1]).
      Now how do we change the solution when we allow negative numbers?
      Imagine that we have both max_prod[i] and min_prod[i] i.e. max prod ending at i and min prod ending at i. Now if we have a negative number at nums[i+1] and if min_prod[i] is negative, then the product of the two will be positive and can potentially be largest product. Key point is to maintain both max_prod and min_prod such that at iteration i, they refer to the max and min prod ending at index i -1.

    You have three choices to make at any position in array.

    1. You can get maximum product by multiplying the current element with
      maximum product calculated so far. (might work when current
      element is positive).
    2. You can get maximum product by multiplying the current element with
      minimum product calculated so far. (might work when current
      element is negative).
    3. Current element might be a starting position for maximum product sub
      array
    class Solution(object):
        def maxProduct(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            max_prod, min_prod, ans = nums[0], nums[0], nums[0]
            for i in range(1, len(nums)):
                x = max(nums[i], max_prod*nums[i], min_prod*nums[i])
                y = min(nums[i], max_prod*nums[i], min_prod*nums[i])            
                max_prod, min_prod = x, y
                ans = max(max_prod, ans)
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.