Maximum Product Subarray

January 2, 2024

Problem #

Given an integer array nums, find the contiguous subarray within the array which has the largest product, and return its product. The subarray must contain at least one number.

Example:

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

Solution #

Algorithm: Dynamic Programming

The key to this problem is to handle the negative numbers. A product of two negative numbers turns positive, and this could potentially be larger than a currently known maximum product.

1. Track Maximum and Minimum Products: At each index in the array, we keep track of the maximum and minimum product up to that index. The reason for keeping track of the minimum product is that a large negative number could be later multiplied by another negative number, making it a large positive.

2. Iterate through the Array:

   • Initialize two variables, maxProduct and minProduct, with the first element of the array. Also, initialize result with the same value.
   • For each element in the array (starting from the second element), calculate the new maximum and minimum products by considering the current element, its product with the previous maximum product, and its product with the previous minimum product.
   • Update result with the maximum of itself and the new maxProduct.

3. Return the Result: The result variable will hold the largest product found.

Python Code #

def maxProduct(nums):
    if not nums:
        return 0

    maxProduct = minProduct = result = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            maxProduct, minProduct = minProduct, maxProduct
        
        maxProduct = max(nums[i], maxProduct * nums[i])
        minProduct = min(nums[i], minProduct * nums[i])

        result = max(result, maxProduct)

    return result

Example Usage #

nums = [2, 3, -2, 4]
print(maxProduct(nums))
# Output: 6

Time Complexity #

• O(n): The solution only requires one pass through the array, making the time complexity linear.

Space Complexity #

• O(1): No additional space is required apart from variables for keeping track of the maximum and minimum products, so the space complexity is constant.

This question effectively assesses a candidate’s understanding of dynamic programming and their ability to handle edge cases in algorithms. It is a suitable medium-difficulty question for technical interviews at companies like Google, Amazon, Meta, and OpenAI.