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.

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.

Iterate through the Array:
 Initialize two variables,
maxProduct
andminProduct
, with the first element of the array. Also, initializeresult
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 newmaxProduct
.
 Initialize two variables,

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 mediumdifficulty question for technical interviews at companies like Google, Amazon, Meta, and OpenAI.