LeetCode 152. Maximum Product Subarray

The Problem

Link to original problem on Leetcode.

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

A subarray is a contiguous subsequence of the array.

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

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

My Solution

Much like 053 Maximum Subarray, we can use dynamic programming with Kadane’s Algorithm to solve this in $O(n)$ time. Check out the solution to that problem for a full explanation of the algorithm and what it’s superior to a naïve approach.

In this implementation, we have to keep track not only of the current maxium number so far, but also the minimum so far. This is because we can have negative numbers, and two negatives multiplied could give us a larger number than the product of the current number and the current maximum.

const maxProduct = nums => {
	let numberTimesMax,
		numberTimesMin,
		currentMax = nums[0],
		currentMin = nums[0],
		best = nums[0];
	for (let i = 1; i < nums.length; i++) {
		// We keep these numberTimesMax and numberTimesMin
		// variables because both values are needed to update
		// currentMax and currentMin. We couldn't successfully
		// updated currentMin if currentMax had already been
		// altered. You could do this with only a numberTimesMax
		// variable, but I like the readability of using both.
		numberTimesMax = currentMax * nums[i];
		numberTimesMin = currentMin * nums[i];
		currentMax = Math.max(numberTimesMax, numberTimesMin, nums[i]);
		currentMin = Math.min(numberTimesMax, numberTimesMin, nums[i]);
		best = Math.max(currentMax, best);
	}
	return best;
};

Credit to AmehPls for his thorough explanation of his own implementation, which I used to update my own from problem 53.