The Blind 75 Leetcode Series: Maximum Product Subarray

Photo by Chris Ried on Unsplash

Today, we are working on 152. Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Given an array of numbers, we want to find the max product of any subarray. We just might want to double check on some constraints:

1. are we guaranteed to see number?
2. for any given product, do we face risk of running out of certain range, say, 32 bit integer?

If the answers are no and no, then we can start.

Naturally, we start with brute force. We check every possible subarray and find max. I’m going to fast-forward this part as we should know how to do that by now.

def maxProduct(nums):
    max_result = float('-inf')
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            result = 1
            for num in nums[i:j+1]:
                result *= num
            max_result = max(max_result, result)
    return max_result

Clearly, we have nested for-loops and we can see how inefficient it is.

What if there’s a way to improve it to linear time?

In order to achieve linear time, we can only go through the list certain time without any nested looping. To do that, we’ll need to have a way to track some intermediate, in-progress result. We’ll have to build it up from smaller problems until we reach the entire list.

Sounds like a job for dynamic programming, but how do we start?

We need to care about some special cases such as

1. zeros
2. odd number of negative numbers in the list
3. even number of negative numbers in the list

We are looking for max product, so this subarray cannot have odd number of negative…