Implement the maximumProductSubarray method that returns the largest product of any continuous subarray.
You are given an integer array that may contain positive numbers, negative numbers, and zero. Your task is to return the maximum product that can be obtained from any continuous subarray.
This is different from maximum sum because multiplying by a negative number can turn the smallest product into the largest product. Therefore, both the maximum and minimum product ending at each index must be tracked.
Example 1
[2,3,-2,4]46Example 2
[-2,0,-1]30Example 3
[-2,3,-4]324Scan the array while keeping two values for the current position: the largest product ending here and the smallest product ending here.
The smallest product is important because if the current number is negative, multiplying it with the smallest previous product may produce the largest product. For each number, calculate the best and worst product using the current value, the previous maximum product, and the previous minimum product.
Update the global answer after processing each value.
Pseudocode:
function maximumProductSubarray(nums, size):
currentMax = nums[0]
currentMin = nums[0]
answer = nums[0]
for i from 1 to size - 1:
value = nums[i]
option1 = value
option2 = value * currentMax
option3 = value * currentMin
newMax = max(option1, option2, option3)
newMin = min(option1, option2, option3)
currentMax = newMax
currentMin = newMin
answer = max(answer, currentMax)
return answer