LC152 - Maximum Product Subarray

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 and the product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Example

Input: nums = [2,3,-2,4]

Output: 6

Explanation: [2,3] has the largest product 6.

Solution

Brute Force

Calculate all subarrays, which has a time complexity of $O(n^3)$ and a space complexity of $O(1)$. We can optimize this approach to $O(n^2)$ by simply caching the calculation results of the previous subarray, but it is not the optimal solution.

Intuition

Do a forwards and backwards pass on the entire array, splitting into a new subarray when a zero is encountered, calculating the product of the subarrays along the way, and saving the maximum values of those. Intuitively, if there are an odd number of negative numbers in a subarray, the greatest sum of that particular subarray comes either before or after that negative number. Hence, we do not need to consider it.

Time complexity of this solution is $O(2n) \approx O(n)$ and we don't use any extra space, so $O(1)$ space complexity .

def maxProduct(self, nums: List[int]) -> int:
	prev = 1
	post = 1
	res = float(-inf)

	for i in range(len(nums)):
		if prev == 0:
			prev = 1
		if post == 0:
			post = 1
			
		prev = prev * nums[i]
		post = post * nums[len(nums)-i-1]
		res = max(res, max(prev, post))

	return res

Kadane's Algorithm

You can calculate the largest sum with Kadane's algorithm in a single pass of the entire array, but this is out of the scope for an interview.