152. Maximum Product Subarray

Description

https://leetcode.com/problems/maximum-product-subarray/

Note: the input array is assumed to have at least one element.

Solution

This is similar to the maximum subarray problem, which can be solved using Kadane's Algorithm. We can use what we learned from that problem and apply it here.

Because this question asks for the product, negative numbers have a different effect. A subarray may flip in and out of the solution as negative numbers are included.

As with the maximum sum subarray, we will keep track of the current and max product. But we will need to keep track of the minimum product too. This is because a negative product may become positive if we encounter another negative number.

Examples

Given an input of: [5, 3, -1, 2, -2, -3, 6]

element	current product & sub array	current min product & sub array	max product & sub array
5	5 [5]	5 [5]	5 [5]
3	15 [5,3]	3 [3]	15 [5,3]
-1	-1 [-1]	-15 [5,3,-1]	15 [5,3]
2	2 [2]	-30 [5,3,-1,2]	15 [5,3]
-2	60 [5, 3, -1, 2, -2]	-4 [2, -2]	60 [5, 3, -1, 2, -2]
-3	12 [2, -2, -3]	-180 [5, 3, -1, 2, -2, -3]	60 [5, 3, -1, 2, -2]
6	72 [2, -2, -3, -6]	-1080 [5, 3, -1, 2, -2, -3, 6]	72 [2, -2, -3, -6]

Given an input of [3, 2, 0, 5, 6, -1]

element	current product & sub array	current min product & sub array	max product & sub array
3	3 [3]	3 [3]	3 [3]
2	6 [3, 2]	2 [2]	6 [3,2]
0	0 [0]	0 [0]	6 [3,2]
5	5 [5]	0 [0, 5]	6 [3,2]
6	30 [5,6]	0 [0, 5, 6]	30 [5,6]
-1	0 [0, 5, 6, -1]	-30 [5, 6, -1]	30 [5, 6]

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # since nums is guaranteed to be not empty, initialize the variables to the first element
        current_product = nums[0]
        max_product = nums[0]
        min_product = nums[0]
        for i in range(1, len(nums)):
            # The current_product is calculated at line 13. However, we need to use the current_product in the min_product calculation.
            # So we need to store the prev_current_product so that value can be used in the min_product calculation
            prev_current_product = current_product
            # This is like Kadane's algorithm where we take the max of either the current_product * the element, or the element. 
            # But now that we have a min_product as well, that value needs to be included too.
            current_product = max(min_product * nums[i], current_product * nums[i], nums[i])
            # Use Kadane like algorithm for the min_product too. Notice we are using the prev_current_product and not the current_product just
            # calculated above.
            min_product = min(min_product * nums[i], prev_current_product * nums[i], nums[i])
            max_product = max(max_product, current_product)
        return max_product