152. Maximum Product Subarray

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.

Note that the product of an array with a single element is the value of that element.

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

First, this is a dynamic programming problem: the product of the array $A$ is related to the product of its subarray $A[0:n-1]$, which is related to the product of the subarray $A[0:n-2]$, which suggests this is a problem with an optimal substructure. The fact that it is a subarray and therefore can exist anywhere inside $A$ as long as it is contiguous means that a DP approach seems like the best way forward.

This problem, however, is unique and therefore quite tricky: unlike most dynamic programming questions, the Bellman Equation is not a scalar field $\mathbb{Z}^n \to \mathbb{Z}$, but a vector field $\mathbb{Z} \to \mathbb{Z}^2$!

To begin, think about just two values $x, y$ and their product $xy$. Assume that $y$ is constant and $x$ is a variable.

1. If $x < 0$, then $y < 0$ gives the largest value for $xy$. Moreover, we want to minimise $x$.
2. If $x > 0$, then $y > 0$ gives the largest value for $xy$. Moreover, we want to maximise $x$.
3. If $x = 0$, then $xy = 0$ regardless.

How do we use this to solve the problem? The approach we can take is to iterate through the array from left to right, calculating the maximum subarray as we go according to the rules above. Our Bellman equation must follow this, and therefore it must track both the minimum and the maximum of the subarrays!

Let $OPT(j) = (OPT_M(j), OPT_m(j)) \in \mathbb{Z} \to \mathbb{Z}^2$ be the maximum and minimum products in the subarray $A[0, j]$. As usual for DP questions, we compare $(OPT_M(j - 1), OPT_m(j - 1))$ and $A[j]$, as well as the products between them. Looking at just $OPT_M(j - 1)$ for now:

• If $A[j] > 0$ and $OPT_M(j - 1) > 0$, then the largest value we can get in $A[0, j]$ is $OPT_M(j - 1)A[j]$.
• If $A[j] < 0$ and $OPT_m(j - 1) < 0$, then the largest value we can get is $OPT_m(j - 1)A[j]$.
• If $A[j] > 0$ and $OPT_M(j - 1) \leq 0$, then the largest value (from a contiguous array) is $A[j]$. This occurs when there is a break in contiguity of the array: since they are either opposite signed or there is a 0 in the calculation, it is better to start calculating starting from $A[j]$.
• Since $OPT_M(j)$ should be the maximum possible answer, we take the largest of our three possible answers.

The same goes for calculating $OPT_m(i, j -1)$ but all the inequalities are flipped, and we take the minimum value. To sum up,

Note that the Bellman equation calculates subarrays that end at a specific index, and thus we can’t simply return $OPT_M(n)$! In fact, we are calculating

We can do a bottom-up approach to calculate that.

def maxProduct(self, nums: List[int]) -> int:
	# matrix storing all min and max of the product subarrays ending at index i
	opts = [[nums[0], nums[0]]]
	
	for i in range(1, len(nums)):
		curr_min = opts[i - 1][0]
		curr_max = opts[i - 1][1]
		
		# Bellman equation
		curr_opt = [
			min(nums[i], nums[i] * curr_min, nums[i] * curr_max),
			max(nums[i], nums[i] * curr_min, nums[i] * curr_max)
		]
		
		# update the matrix
		opts.append(curr_opt)
	
	return max(opt[1] for opt in opts)

We can simplify this further.

• Notice that we only use opts[i] once, to calculate opts[i + 1]. Thus, we can just use two variables curr_min, curr_max to do the calculations instead. Notice that they call each other in their calculations, so variable assignment must take place concurrently or temporary values must be used.
• Similarly, we are calculating the maximum subarray $A[0, j]$ at each iteration, and then finding the maximum by iterating through our list a second time. We can simply store the largest seen at each iteration to get the maximum.

def maxProduct(self, nums: List[int]) -> int:
	largest = float('-inf')
	curr_min, curr_max = nums[0], nums[0]
	
	for i in range(1, len(nums)):
		curr_min, curr_max = (
			min(nums[i], nums[i] * curr_min, nums[i] * curr_max),
			max(nums[i], nums[i] * curr_min, nums[i] * curr_max)
		)
		
		largest = max(curr_max, largest)
	
	return largest

Top-down Approach

A top-down approach starts with the Bellman Equation, calculating

where $(OPT_M(0), OPT_m(0)) = (0, 0)$, and

def maxProduct(self, nums: List[int]) -> int:
	def maxSubProduct(j: int) -> (int, int):
		if j == 0:
			return nums[0], nums[0]
			
		prev_min, prev_max = maxSubProduct(j - 1)
		
		curr_min, curr_max = (
			min(nums[i], nums[i] * prev_min, nums[i] * prev_max),
			max(nums[i], nums[i] * prev_min, nums[i] * prev_max)
		)
		
		return curr_min, curr_max
	
	# ...

This is where memoisation comes in. We only want to calculate maxSubProduct(i) once for each i, but maxSubProduct(i) calls maxSubProduct(i-1) every time. Therefore we memoise the calculated value to ensure there is no duplicate calculation.

def maxProduct(self, nums: List[int]) -> int:
	memo = {0: (nums[0], nums[0])}
	
	def maxSubProduct(i: int) -> (int, int):
		if i in memo:
			return memo[i]
			
		prev_min, prev_max = maxSubProduct(i - 1)
		
		curr_min, curr_max = (
			min(nums[i], nums[i] * prev_min, nums[i] * prev_max),
			max(nums[i], nums[i] * prev_min, nums[i] * prev_max)
		)
		
		memo[i] = (curr_min, curr_max)
		return curr_min, curr_max
	
	largest = float('-inf')
	for i in range(0, len(nums)):
		largest = max(largest, maxSubProduct(i)[1])
	
	return largest

Time Complexity

There is a for loop with constant time operation per iteration: the min and max comparisons are all fixed length, and the other operations are simply variable assignments or multiplication. This loops for $\mathcal{O}(n)$ iterations. The rest are constant time operations, so the algorithm runs in $\mathcal{O}(n)$ time.

Space Complexity

There are only 3 variables used to calculate the product, so the algorithm has $\mathcal{O}(1)$ space complexity.