Skip to main content

Maximum Product Subarray

Problem Statement​

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Leetcode link

Example 1:​

Input: nums = [2,3,-2,4]
Output: 6

Explanation: [2,3] has the largest product 6.

Example 2:​

Input: nums = [-2,0,-1]
Output: 0

Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Output: 0

Constraints​

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Code​

Python3 Code

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums: return
        left, right, record = 0, 0, -float('inf')
        for i in range(len(nums)):
            left = (left or 1) * nums[i]
            right = (right or 1) * nums[-i-1]
            record = max(record, left, right)
        return record