[Java] Max subarray product

Given an array of integers, find the maximum subarray product. The product of all elements in the array is guaranteed to fit in an integer.

Example:

-2,0: return 0

-2,20,-1: return 40

1,2,3: return 6

This is a similar problem to max subarray sum (Kadane's algorithm), however, in that problem we restarted our max search when adding a new element to the sum so far was worse than picking the new element alone.

Example:

10,-2,20
We want to pick the -2 since 28 (10 + -2 + 20) > 20 (20)

-2,20
We want to discard the 2 since 18 (-2 + 20) < 20 (20)

This is true since sum of negatives is always negative

In this problem instead multiplication of negatives is a positive, therefore:
-2,20,-1
We want to pick both -2 and -1 since product 40 (-2 * 20 * -1) > 20 (20)

So we shouldn't discard too early a negative value as in the sum problem. Specifically:
- as long as items so far are positive, we want to pick all of them
- if items so far have an even number of negatives, we want to pick all of them
- if items so far have an odd number of negatives, we might want to wait and see if there is another negative later on, in which case we pick all, otherwise we pick the maximum subarray without at least one of the negatives

What this means is at each moment, we don't keep a max so far only, but also a min so far as an incoming negative number might transform the min so far to the global maximum, as in the example above.

As with Kadane's case, we don't need to keep a whole array of elements as at each step we only look at the previous sum, which in our case is the product and specifically the pair (min, max)

An edge case which didn't affect the sum problem is 0. In that instance, the sum would be unaltered, but the product would become zero and stay like that forever.

Therefore, when the current element is 0, we are forced to break our subarray and restart. However, 0 could be a result in itself, for example:
-2,0 or 0,-2
0 is the largest subarray product

so if the global maximum up to 0 is < 0, then 0 is our answer. We then reinitialize both max so far and min so far to 1

At each moment we make a choice:

• current element is 0: if global max until then was 0, set 0 as best result, max so far = 1, min so far = 1 and continue
• current element is not 0: calculate max * current and min * current, this will cover the cases where we had picked an odd number of negatives and now found another negative which would make the product positive. Then determine for the NEXT element: max = maximum(max, min, current) and min = minimum(max, min, current)  

This works in O(N) time and O(1) space.

You can check my implementation of maxProdSubarray on my Gist along with some tests in MaxProdSubarrayJTests.