Leetcode 152 - Maximum Product Subarray

Table of contents

Problem

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.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Explanation/Approach

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.

• Dynamic Programming: The key is to keep track of both the maximum and minimum product up to the current position, as a negative number can turn a minimum product into a maximum.

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.

Explanation

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 product of the current number and the previous maximum product (which might become the new maximum or minimum).
• The product of the current number and the previous minimum product (as a negative number can turn a small number into a large one).
• The current number itself (as starting a new subarray from this number might be more beneficial).

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.