Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
The description was taken from https://leetcode.com/problems/maximum-product-subarray/.
#O(N) Time, O(1) Spaceclass Solution: def maxProduct(self, nums: List[int]) -> int: if len(nums) == 0: return 0 running_min = nums[0] running_max = nums[0] result = nums[0] for i in range(1, len(nums)): temp_max = max(nums[i], running_max * nums[i], running_min * nums[i]) running_min = min(nums[i], running_max * nums[i], running_min * nums[i]) running_max = temp_max result = max(running_max, result) return resultSince this falls in line with other greatest subarray problems, we can solve this problem with a variation of Kadane's Algorithm.
Unlike the subarray sum version of this problem where we just needed to see if each previous element was positive to create the best running maximum subarray, we need to be craftier here to handle negative numbers.
One very low negative number could wreck a subarray product. However, two very low negative numbers could make a very large product that would maximize a subarray product. We will take care of this by keeping track of a minimum number which could possibly be a very low negative number. By doing this, if we have a second negative number then we can maximize a subarray product.
We will start by checking if we have been given an empty array. We'll return zero if it is because there could be no subarrays.
if len(nums) == 0: return 0
Next, we will initialize our running maximum value, our running minimum value, and our result value to the first element within the input array.
running_min = nums[0] running_max = nums[0] result = nums[0]
Similar to the conventional version of Kadane's Algorithm, we will traverse the input array and check the product between the current iteration's element and the previous element to find the maximum. We initialized these three values with the first index in the previous iteration so we'll be starting at the second index for our traversal.
for i in range(1, len(nums)):
During each iteration, we will take a temporary maximum value, choosing between our current element, our current element multiplied by the running maximum, and the current element multiplied by the running minimum.
temp_max = max(nums[i], running_max * nums[i], running_min * nums[i])
Why are we considering these three values for the maximum?
We will want to consider the current element as the maximum in case the previous elements have been low values. For example, if our first element was a negative one or a zero and our current value was a two, then we would want our running maximum to be two, rather than negative two or zero.
We will want to consider the current element multiplied by the running maximum in case the previous elements have been positive. This is the straightforward edge case.
We will want to consider the current element multiplied by the running minimum in case our running maximum value is negative and the running minimum is also negative.
The reason we have the temp_max value and a running_max value is because if we only had the running_max variable, then when we consider running_max * nums[i] during our running_min calculation, we would be multiplying the running maximum value we just calculated in the same iteration, rather than the previous one. This would give us an incorrect minimum.
Next, let's calculate the smallest minimum between the three previously mentioned considerations.
running_min = min(nums[i], running_max * nums[i], running_min * nums[i])
We want to keep calculating this value in every iteration and roll this minimum valued snowball into a giant negative number if possible. By doing this, if we were in another iteration where our current number was also negative, then we could throw the giant negative valued snowball on the top of a negative number and make a large, positive product.
We will then set our running maximum as the temporary maximum value so that it can be used in the running minimum calculation during the next iteration without being overwritten in the previous step.
running_max = temp_max
Afterward, we will test if our running maximum is greater than any maximum values we have seen before. We will update our result with it if that is true.
result = max(running_max, result)
Once we have traversed the entire array, we will return the maximum product subarray's value.
return result