Skip to main content

Maximum Product Subarray

Problem Description​

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.

Constraints​

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

Code in Different Languages​

Written by @mahek0620
 class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0

max_prod = nums[0]
min_prod = nums[0]
result = max_prod

for num in nums[1:]:
if num < 0:
max_prod, min_prod = min_prod, max_prod

max_prod = max(num, max_prod * num)
min_prod = min(num, min_prod * num)

result = max(result, max_prod)

return result



References​