# September LeetCoding Challenge, Day 11: Maximum Product Subarray

September 13, 2020The 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: