Leetcode - Maximum Product Subarray

Leetcode : Maximum Product Subarray

Description

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

Example 2

Input

[-2,0,-1]

Output

0

Approach

The presence of negative number and zero within the list can quickly change the values of maximum and minimum number. Hence, the program must compare every possible values - current, current * min, current * max

Solution (Python)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxSub = nums[0]
        minSub = nums[0]
        result = nums[0]
        
        for i in range(1, len(nums)):
            curr = nums[i]
            
            tempMax = max(curr, maxSub * curr, minSub * curr)
            minSub = min(curr, maxSub * curr, minSub * curr)
            
            maxSub = tempMax
            
            result = max(maxSub, result)
        
        return result