LeetCode 152. Maximum Product Subarray

Description

https://leetcode.com/problems/maximum-product-subarray/

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

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

Explanation

need to keep track of min product and max product because both positive and negative numbers exist.

Python Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        result = nums[0]
        min_product = max_product = 1
        
        for num in nums:
            choices = num, min_product * num, max_product * num
            max_product = max(choices)            
            min_product = min(choices)            
            result = max(result, max_product)
        
        return result
  • Time complexity: ~N
  • Space complexity: ~1

Leave a Reply

Your email address will not be published.