Why does this maximum product subarray algorithm work?

Question

The problem is to find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product 6.

Why does the following work? Can anyone provide any insight on how to prove its correctness?

if(nums == null || nums.Length == 0)
{
    throw new ArgumentException("Invalid input");
}

int max = nums[0];
int min = nums[0];
int result = nums[0];

for(int i = 1; i < nums.Length; i++)
{
    int prev_max = max;
    int prev_min = min;
    max = Math.Max(nums[i],Math.Max(prev_max*nums[i], prev_min*nums[i]));
    min = Math.Min(nums[i],Math.Min(prev_max*nums[i], prev_min*nums[i]));
    result = Math.Max(result, max);
}

return result;

Answer 1

Start from the logic-side to understand how to solve the problem. There are two relevant traits for each subarray to consider:

• If it contains a 0, the product of the subarray is aswell 0.
• If the subarray contains an odd number of negative values, it's total value is negative aswell, otherwise positive (or 0, considering 0 as a positive value).

Now we can start off with the algorithm itself:

Rule 1: zeros

Since a 0 zeros out the product of the subarray, the subarray of the solution mustn't contain a 0, unless only negative values and 0 are contained in the input. This can be achieved pretty simple, since max and min are both reset to 0, as soon as a 0 is encountered in the array:

max = Math.Max(0 , Math.Max(prev_max * 0 , prev_min * 0));
min = Math.Min(0 , Math.Min(prev_max * 0 , prev_min * 0));

Will logically evaluate to 0, no matter what the so far input is.

arr:    1  1  1  1  0  1  1  1  0  1  1  1  0  1  1  0
result: 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
min:    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
max:    1  1  1  1  0  1  1  1  0  1  1  1  0  1  1  0
//non-zero values don't matter for Rule 1, so I just used 1

Rule 2: negative numbers

With Rule 1, we've already implicitly splitted the array into subarrays, such that a subarray consists of either a single 0, or multiple non-zero values. Now the task is to find the largest possible product inside that subarray (I'll refer to that as array from here on).

If the number of negative values in the array is even, the entire problem becomes pretty trivial: just multiply all values in the array and the result is the maximum-product of the array. For an odd number of negative values there are two possible cases:

1. The array contains only a single negative value: In that case either the subarray with all values with smaller index than the negative value or the subarray with all values with larger index than the negative value becomes the subarray with the maximum-value
2. The array contains at least 3 negative values: In that case we have to eliminate either the first negative number and all of it's predecessors, or the last negative number and all of it's successors.

Now let's have a look at the code:

max = Math.Max(nums[i] , Math.Max(prev_max * nums[i] , prev_min * nums[i]));
min = Math.Min(nums[i] , Math.Min(prev_max * nums[i] , prev_min * nums[i]));

Case 1: the evaluation of min is actually irrelevant, since the sign of the product of the array will only flip once, for the negative value. As soon as the negative number is encountered (= nums[i]), max will be nums[i], since both max and min are at least 1 and thus multiplication with nums[i] results in a number <= nums[i]. And for the first number after the negative number nums[i + 1], max will be nums[i + 1] again. Since the so far found maximum is made persistent in result (result = Math.Max(result, max);) after each step, this will automatically result in the correct result for that array.

arr:     2   3   2  -4   4   5
result:  2   6  12  12  12  20
max:     2   6  12  -4   4  20  
//Omitted min, since it's irrelevant here.

Case 2: Here min becomes relevant too. Before we encounter the first negative value, min is the smallest number encountered so far in the array. After we encounter the first positive element in the array, the value turns negative. We continue to build both products (min and max) and swap them each time a negative value is encountered and keep updating result. When the last negative value of the array is encountered, result will hold the value of the subarray that eliminates the last negative value and it's successor. After the last negative value, max will be the product of the subarray that eliminates the first negative value and it's predecessors and min becomes irrelevant. Now we simply continue to multiply max with the remaining values in the array and update result until the end of the array is reached.

arr:    2   3   -4    3    -2    5     -6    3
result: 2   6    6    6   144  770    770  770
min:    2   6  -24  -72    -6  -30  -4620  ...
max:    2   6   -4    3   144  770    180  540 
//min becomes irrelevant after the last negative value

Putting the pieces together

Since min and max are reset every time we encounter a 0, we can easily reuse them for each subarray that doesn't contain a 0. Thus Rule 1 is applied implicitly without interfering with Rule 2. Since result isn't reset each time a new subarray is inspected, the value will be kept persistent over all runs. Thus this algorithm works.

Hope this is understandable (To be honest, I doubt it and will try to improve the answer, if any questions appear). Sry for that monstrous answer.

Answer 2

Lets take assume the contiguous subarray, which produces the maximal product, is a[i], a[i+1], ..., a[j]. Since it is the array with the largest product, it is also the one suffix of a[0], a[1], ..., a[j], that produces the largest product.

The idea of your given algorithm is the following: For every prefix-array a[0], ..., a[j] find the largest suffix array. Out of these suffix arrays, take the maximal.

At the beginning, the smallest and biggest suffix-product are simply nums[0]. Then it iterates over all other numbers in the array. The largest suffix-array is always build in one of three ways. It's just the last numbers nums[i], it's the largest suffix-product of the shortened list multiplied by the last number (if nums[i] > 0), or it's the smallest (< 0) suffix-product multiplied by the last number (if nums[i] < 0). (*)

Using the helper variable result, you store the maximal such suffix-product you found so far.

(*) This fact is quite easy to proof. If you have a different case, for instance there exists a different suffix-product that produces a bigger number, than together with the last number nums[i] you create an even bigger suffix, which would be a contradiction.