Leetcode: Maximum product subarray
Given an array
nums with integer values
-10 <= x <= 10, calculate the maximum consecutive product. For example, the array
[2,3,-1,4] produces the maximum product
The first obsveration that we can make is that whenever a
0 is encountered, it sets the whole product to
0. This means, if a
0 is somewhere in the middle of the array, we need to look at the left and right part individually because they cannot be connected.
Secondly, an odd amount of negative numbers makes the whole product negative. Having
6, … negative numbers will keep the product at the same amount (if all of them are
-1) or increase it.
Finally, since those numbers are all integers, the longer the chain of multiplied numbers, the higher to outcome.
The algorithm that I came up with iterates twice over the whole array and has a time complexity of
O(n) and constant space complexity
O(1). Given the following example
[2,-2,3,-2,0,9] we can define two pointers,
j and two helper variables,
current_product. We start at position
0,0, then move the
j pointer to the right and multiply the numbers that we encounter until we hit a
0. This way we slowly increment our product. At each step we compare the current product with the overal maximum. Once we reach the end or
0, we move
i to the right and divide at each step until we reach
j. If we reached a
0 we add this as possible maximum and then jump with
j over the
0, starting the above process again.
The Python code handles some more corner cases, for example if there’s only one element, and looks like this: