Math Dynamic Programming
Proficient Level

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
Input:
nums (int[]) = [2,3,-2,4]
size (int) = 4
Return:
(int) 6
Example 2
Input:
nums (int[]) = [-2,0,-1]
size (int) = 3
Return:
(int) 0
Example 3
Input:
nums (int[]) = [-2,3,-4]
size (int) = 3
Return:
(int) 24

Scan 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
Run your code to see the result.