Leetcode 152. Maximum Product Subarray

Problem

Leetcode 152 - Maximum Product Subarray

Example:

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

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

Approach

We can solve this problem using Dynamic Programming. The idea is to keep track of both the prefix and suffix at each position

Here is the Python code for the solution:

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n, res = len(nums), nums[0]
        prefix = suffix = 0

        for i in range(len(nums)):
            prefix = nums[i] * (prefix or 1)
            suffix = nums[n-1-i] * (suffix or 1)
            res = max(res, max(prefix, suffix))
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$