Leetcode 152 - Maximum Product Subarray

Prompt: Given a list of integers, we want to find a subarray of integers where the product of all integers in the subarray is the max product compared to all other products from other subarrays.

Example:

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.

Solution: Since we are tracking subarrays we can split the problem into subproblems. This allows us to use DP. First, we need to visualize the problem:

List of integers = [2,3]

Subarrays:

From left to right
[2] = 2 
[2,3] = 2 x 3

From right to left
[3] = 3 
[3,2] = 3 x 2

We noticed that all subarrays are created by adding to an empty array from left to right and also right to left. We also noticed that the product of each subarray is the product of the previous subarray and the newly added integer.

[0,3] = 0 x 3

Not quite right, the maximum product should be 3 but it is 0.

We also noticed that if the previous product is 0, we can just assign the current product to be the current integer.

Knowing that, we can solve this with bottom up tabulation. We can create a copy of the original list. Then, we can update the original list from left to right with the product of its subarray. To get the product of each subarray, we can just multiply the current integer with the product of the previous subarray.