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.

Answer 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;
}

Answer 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