# September LeetCoding Challenge, Day 11: Maximum Product Subarray

September 13, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 11 is Maximum Product Subarray. You’re given a non-empty array of integers nums and are interested in finding the contiguous non-empty subarray which has the largest product. You’re not given any limits on the size of nums.

Since we’re not given any limits on the size of nums, I didn’t assume that the naive algorithm of checking all possible subarrays in $$\mathcal{O}(n^3)$$ (possibly reducing to $$\mathcal{O}(n^2)$$ using dynamic programming) would work. Instead, I tried to find an algorithm whose time complexity would match the theoretical lower bound of $$\mathcal{O}(n)$$. Some relevant observations are:

• If the array has a single element, then the maximum product will be that element;
• If the array has more than one element, then the maximum product subarray will contain an even number of negative integers, so that it is either positive or 0;
• If there’s at least one non-empty subarray without a 0 with an even number of negative integers, then the maximum product will never be 0.

Based on the previous observations, we can derive an $$\mathcal{O}(n)$$ algorithm to solve this problem. The idea is to iterate through all the values of nums, keeping track of, for the product of a non-empty subarray ending at that number, the largest possible positive number and the smallest possible negative number. When visiting a new number, if the number is 0, we reset both these values. If the number is positive, both the largest positive number and smallest negative number are multiplied by that number. If the number is negative, the largest possible positive number becomes the multiplication of the smallest negative number with that number, and vice-versa for the smallest possible negative number. The largest positive number at each iteration (or 0) is the largest product of a non-empty subarray ending at that number. The following is an implementation of that idea: