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.

Examples

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