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. Tags: Array

Try It!

Discussion

Video

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_prod = nums[0]
        prev_max = nums[0]
        prev_min = nums[0]

        for num in nums[1:]:
            cur_max = max(num, num * prev_max, num * prev_min)
            cur_min = min(num, num * prev_max, num * prev_min)
            max_prod = max(max_prod, cur_max)
            prev_max = cur_max
            prev_min = cur_min
        return max_prod