To solve this problem efficiently, we want to do a single pass through the array. We can use a sliding window approach, where we walk left to right, and include more numbers in the product.

This is made complicated by the fact that we can multiply by negative numbers. The thing to realize is that the product always increases in magnitude, even if its sign changes to positive or negative. This means the highest product will always come after a really big positive product or a really big negative product.

Here's an example of this:

This means to solve the problem, we have to remember the maximum and minimum products that we've seen in the current window, because the maximum and the minimum are bounds on the magnitude so far. Even though this is an iterative problem, the easiest way to come up with the for-loop that we'll write is to use recursion.

1. Recursion

Here's the recursion for the max and min product in the current window. It can either involve the previous min product, the previous max product, or start over at the current element.

Here's the recursion for the minimum product in the window when we're standing at index i. It's the same, but with a min instead:

2. Base case

The recursion calls itself on smaller and smaller i. When the recursion gets to i=0, we know the max and min products are both the 0th element.

3. Code

Intuitively, you can code this up by computing minProd and maxProd as you go left to right. Formally, what we're really doing is Dynamic Programming with "Tabulation+" - see the Dynamic Programming lesson if you need a refresher on this.

We'll also keep track of the maximum product we've ever seen, maxSeen, and we'll return it as our solution. Here's the code:

Time Complexity $O(n)$. We loop through the entire array, and do O(1) operations in each iteration. This is a total of O(n) time.

Space Complexity $O(1)$. We store 4 numbers which is O(4) = O(1) space.