Solution: Maximum Product Subarray

Statement

Given an integer array, nums, find a subarray that has the largest product, and return the product.

Constraints:

• $1\leq$nums.length $\leq 10^3$

• $-10\leq$nums[i] $10$

• The product of any prefix or suffix of nums is guaranteed to fit in a $32-bit$ integer.

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach is to calculate the product of every combination of contiguous subarrays and return the maximum of all the products.

Since we have to iterate over the array using a nested loop to find every combination, the time complexity of this approach will be $O(n^2)$, where$n$is the size of the array nums.

Optimized approach using dynamic programming

The maximum product subarray problem can be solved more efficiently using dynamic programming by dividing the array and solving the subproblems. In this case, we can find the maximum product of a subarray from the start to any element by using the maximum product of the subarray from the start to its previous element. Using this approach, we don’t need to calculate the previous products again; instead, we can use them from the stored products.

The simplest case is when the numbers in the array nums are all positive numbers. In that case, we calculate the maximum product by multiplying all the numbers to get the result. When we encounter zeros or negative numbers in the array, we have to use a slightly different approach, as explained below:

• Zeros will reset the product to $0$. If the result is less than the product, update it with the product. Otherwise, the result remains the same.

• Negative numbers can be a little challenging. When multiplied, a single negative number can flip the larger product into a smaller number. However, if we get another negative number, we can get the larger product again. Unlike zero, here we have a chance that our larger product can be restored if negative numbers are encountered twice.

To solve the problem above, follow the steps below:

1. Initialize max_so_far with the first element of nums. It will be used to track the maximum product up to an element. Initialize min_so_far with the first element of nums. It will be used to track the minimum product up to an element. Initialize result with max_so_far.

2. Now, iterate through the rest of the elements of the array as follows:

   1. Update max_so_far and min_so_far by taking the maximum and minimum of the current value, the product of max_so_far and the current value, and the product of min_so_far and the current value, respectively.

   2. Update result by taking the maximum of max_so_far and result.

3. When all elements have been traversed, return result.

Let’s look at the following illustration to get a better understanding of the solution: