The max product of consecutive elements in an array

Question

I was asked this algorithm question during my onsite interview. Since I was not asked to sign NDA, I post it here for an answer.

Given an array of REAL numbers that does not contain 0, find the consecutive elements that yield max product. The algorithm should run in linear time

I have considered the following approach: Use two arrays. First one is to use DP idea to record the current max absolute value product, the second array to record the number of negative elements met so far. The final result should be the largest max absolute value and the number of negative numbers be even.

I thought my method will work, but was interrupted during coding saying it will not work. Please let me know what is missing in the above approach.

Solution 1

The algorithm is indeed O(n). When iterating the array, use a variable to store the max value found so far, a variable to store the max value of subarray that ends at a[i], and another variable to store minimum value that ends at a[i] to treat negative values.

float find_maximum(float arr[], int n) {
    if (n <= 0) return NAN;

    float max_at = arr[0];  // Maximum value that ends at arr[i]
    float min_at = arr[0];  // Minimum value that ends at arr[i]
    float max_value = max_at;

    for (int i = 1; i < n; i++) {
        float prev_max_at = max_at, prev_min_at = min_at;
        max_at = max(arr[i], arr[i] * prev_min_at, arr[i] * prev_max_at);
        min_at = min(arr[i], arr[i] * prev_min_at, arr[i] * prev_max_at);
        max_value = max(max_value, max_at);
    }
    return max_value;
}

Solution 2

You can implement a variant of the Kadane algorithm (http://en.wikipedia.org/wiki/Maximum_subarray_problem) who runs with constant extra memory and linear in the size of the problem (no extra array,...)

If only strict positive numbers are given:

def max_subarray_mul(A):
    max_ending_here = max_so_far = 1
    for x in A:
        if x > 0
            max_ending_here = max(1,max_ending_here*x)
            max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

I'm still working on the part with negative numbers

Or a more expensive (in time) method is the following, but this will work with negative numbers:

def max_subarray_mul(A):
    max_so_far = 1
    n = length(A)
    for i in 1...n:
        x = A[i]
        tmp = x
        max_so_far = max(max_so_far,tmp)
        for j in i+1...n:
          tmp = tmp*A[j]
          max_so_far = max(max_so_far,tmp)
    return max_so_far

Which runs in constant memory and O(n²) time

Comments

[IVlad]

Hint: assume you only have positive numbers. What does the problem reduce to if you take the logarithm (any base) of each number? Now, how can you handle negative numbers as well?

[Hot Licks]

Given the requirement for consecutive elements, and assuming an odd number of negatives, you'd need to try from both ends.

[Hot Licks]

(This is assuming that "consecutive elements" has an implied "N" in front of it, not an implied "2".)

[Willem Van Onsem]

Are negative values allowed?

[glagolig]

Doesn't REAL mean floating-point? I do not understand why everyone is assuming INTEGER.

[Jin]

@Gupta, in your case, it should be 120, [4,5,6] is the answer

[Jin]

@Gupta: there should not be a 0 in your example, as I mentioned explicitly. Also, the array should be size>1

[Shashank]

Thank you. I am trying to use @IVlad's hint to come up with a solution. So far I have figured out that if all numbers are positive, then the problem reduces to taking the log(anybase) of every number in the array and then finding the max sum of consecutive elements of the array. However I have not yet thought of a way to handle negative numbers. I am working on it.

[Hot Licks]

You're not making sense. How does using logs make it any different from simply multiplying? And, assuming an even number of negatives, why wouldn't the solution just be the product of all elements in the array? And with odd negatives it would be the product up to the last negative, starting from either end.

[Hot Licks]

(Ah, yes! Since these are real one needs to be concerned about values less than 1 (but still positive). That does make it messier.)

[justhalf]

Btw Jin, this is probably why your solution does not work: you don't know from which subarray the maximum value comes from, and hence you don't know how many negative numbers are there. consider the array [2, -0.7, 2, 2]. Your DP will produce [2, 2, 2.8, 5.6] and the count of negative numbers [0, 1, 1, 1] and so your output will be 2 where it should be 4 (note that 4 does not even appear in your DP array).

[justhalf]

Btw, are you sure that the problem wants you to multiply at least two elements? I'm a bit unsure on this since the original maximum subarray problem allows a single element sum, which is not the case here. Note that the product of one number is the number itself. So don't you think for the case [2, 60, 0.0001, 121] the answer should be 121?

[IVlad]

if x > 0, max_ending_here, assuming it means what its name implies, can be just x itself and not max_ending_here*x. For example: 0.3 2.2. 0.3 * 2.2 < 2.2.

[Shashank]

Really nice job. O(n) and extremely simple as well. I was thinking way too hard. Kudos to you and +1 sir.

[justhalf]

Although this one will output 0.1 for [0.1, -3, 0.1], which I believe should be the case, not as OP has mentioned

[Shashank]

@justhalf Well even if it's not the case then he could just edit the arguments to his max function and take out arr[i] and it would work if the subarray must be at least two elements.

[Chen Pang]

If you are saying the product must be at least of two elements, we can simply update the algorithm: In the beginning: max_at = arr[0] * arr[1]; Then: max_at = max(arr[i] * arr[i-1], arr[i] * prev_min_at, arr[i] * prev_max_at); The same for min_at

[justhalf]

@Shashank: Nope. How about the array in the comments: [60, 2, -0.000000001, 99999] or basically any array containing single isolated highest element

[justhalf]

@Echevil: yes, I'm not saying that we can't update it. It's just we might need to clarify this with OP, and if it's really at least two elements, then we do need to update the code. That's my point. =D

[Shashank]

He accounts for "single isolated highest element" by including arr[i] as an argument to his max function. His code is just fine and easily modifiable to make it work with a bound of length(subarray) >=2.

[justhalf]

@Shashank, yes, his code is fine and easily modifiable, I agree. I'm just making my point to your (apparently edited) comment that we can just simply consider special case of two elements. =)

[FaceBro]

This is correct, passed all leetcode test case.. Cool

[Stef]

Counter-example: A = [5, 0.1]. Then max(A[0..x]) == A[0..0] == 5 and min(A[0..y]) == A[0..1] == 5 * 0.1 == 0.5. Thus your method gives result 5 / 0.5 == 10.0 when the actual solution should be 5.