#107 Medium Time O(n) Space O(1) Animated

Maximum Product Subarray

Find the contiguous subarray with the largest product.

LeetCode ↗

Approach: Dynamic Programming (1D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Find the contiguous subarray with the largest product.

Constraints

Time Complexity: O(n)
Space Complexity: O(1)

Solution — Dynamic Programming (1D)

O(n) O(1)

def maxProduct(nums):
    res = max(nums)
    curMin, curMax = 1, 1
    
    for n in nums:
        if n == 0:
            curMin, curMax = 1, 1
            continue
            
        tmp = curMax * n
        curMax = max(n * curMax, n * curMin, n)
        curMin = min(tmp, n * curMin, n)
        res = max(res, curMax)
        
    return res

Coin Change

Word Break

Maximum Product Subarray

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (1D)