Skip to content

Leetcode 152 - Maximum Product Subarray

Difficulty: medium

Table of contents

Open Table of contents


Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

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

Example 2:

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



This problem requires finding the subarray with the largest product in an array of integers. It is a variation of the maximum subarray problem but involves handling negative numbers, which can become positive by another negative number.

Solution: Dynamic Programming

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0

        res = max(nums)
        cur_min, cur_max = 1, 1

        for n in nums:
            temp = (cur_max * n, cur_min * n, n)
            cur_max = max(temp)
            cur_min = min(temp)
            res = max(res, cur_max)

        return res

Time and Memory Complexity

The time complexity remains O(n), as this solution still involves a single pass through the array. The space complexity is O(1) since it uses a fixed number of variables.


This solution keeps track of the current maximum and minimum products at each element, considering the possibility of a number being negative. The key insight is that a negative number can flip the maximum and minimum products. Hence, at each step, it calculates the maximum and minimum products by considering:

The final result is the maximum of the current result and the current maximum product. The improvement in this solution comes from the use of a tuple to simplify the calculation of the current maximum and minimum products and the updating of these values in a more concise manner.