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