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

This answer assumes all numbers are positive.

A one-liner solution in python:

from itertools import accumulate

def max_prod(a):
    return max(accumulate(a, lambda x,y: max(x*y, 1), initial=1))

This is O(n)-time and O(1)-space.

This algorithm uses itertools.accumulate to compute accumulated products from the beginning of the array, dropping back to the empty product 1 if a result is ever lower than 1. Then, we return the maximum product found.

We can test the correctness of the algorithm by generating arrays of random numbers and comparing with a bruteforce solution:

from math import prod
from numpy import random

def brute_force(a):
    return max(prod(a[i:j]) for i in range(len(a)) for j in range(i,len(a)+1))

for _ in range(1000):
    a = random.random(10) * 3 # array of 10 floats in [0.0..3.0]
    p1 = max_prod(a)
    p2 = brute_force(a)
    if p1 != p2:
        print(a)
        print(list(accumulate(a, lambda x,y: max(x*y, 1), initial=1)))
        print(p1, p2)
        print()

Answer 2

If we want to solve in O(n) and allowed to take two traversals of array and o(n) extra space, my below code would work for all +ve and -ve values in Java.

import java.util.ArrayList;
import java.util.List;

public class largestProductOfTwoNumbers {

    public static void main(String[] args) {
        int result = 0;
        int a[] = { -22, -5, 12, 6, 3, 4, 9, -11, 4, 5, 6, 8, 7, 7 };
        int max = 0;

        int curr = 0;
        List<Integer> list = new ArrayList();

        for (int i = 0; i < a.length - 1; i++) {

            curr = a[i] * a[i + 1];
            list.add(curr);

        }

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > max) {
                max = list.get(i);
            }

        }
        System.out.println(max);
    }
} 

Answer 3

I wrote below code, for finding maximum product of adjacent integer values in input array, assuming the product would also be in the int range it would iterate the loop n/2 times only

int adjacentElementsProduct(int[] inputArray) {

    int maxProdct=inputArray[0]*inputArray[1];
//as we have already taken product of first two , start from 3rd and iterate till second last because we are checking the product of i+1 for every i
    for (int i=2; i<inputArray.length-1; i=i+2){
        if(inputArray[i-1]*inputArray[i] >inputArray[i]*inputArray[i+1]){
            if(inputArray[i-1]*inputArray[i]>maxProdct)
                maxProdct =inputArray[i-1]*inputArray[i];
        }
        else if(inputArray[i+1]*inputArray[i] > maxProdct)
            maxProdct=inputArray[i+1]*inputArray[i];



    }
//if its an even array the last element would have been covered while calculating product with second last, otherwise we would check the product for last and second last element and compare with maxProduct
    if(inputArray.length%2 !=0){
        if(maxProdct<inputArray[inputArray.length-1]*inputArray[inputArray.length-2]){
            maxProdct=inputArray[inputArray.length-1]*inputArray[inputArray.length-2];
        }
    }
    return maxProdct;

}

Answer 4

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

Answer 5

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 6

In O(n) result. Find the consecutive elements that yield max product, by multiplying each element from left to right and saving them in a list. If the new product is bigger than the last multiply the next element and update the list. If not start a new list and repeat. Algorithm in Python 3.3 :

import numpy as np

x = [-500,-400,200,0.1,-100,20,-10,2]

prod_seq_lists = [[x[0], x[1]]]  # Start assuming the first 2 elements have max product and save them in a list
product_result = []  # Contains the product of each list


for e in x[2:]:  # Start for loop from 3rd element
    if x[0] == 0 or x[1] == 0 or e == 0:  # Raise error if there's a 0
        raise IndexError('Found 0')

    temp_b = np.prod(prod_seq_lists[-1])  # Calculate the product of the last list in max_prod_seq
    temp_a = temp_b * e  # Multiply the new_element

    if temp_a >= temp_b:  # If last_list*new_element >= last_list
        prod_seq_lists[-1].append(e)  # Append the new_element in your last_list

        if e == x[-1]:
            product_result.append(temp_a)  # Save the product of the last list

    else:
        product_result.append(temp_b)  # Save the product of each list
        prod_seq_lists.append([e])  # Else, append append the new element in a new_list


print("Your array: ", prod_seq_lists)
print("The list with max product of consecutive elements: ", prod_seq_lists[np.argmax(product_result)])  # Get index of the maximum product and print that list
print("The max product of consecutive elements: ", max(product_result))

Returns :

Your array:  [[-50, -40, 20], [0.1], [-100], [20], [-10], [90, 1000]]
The list with max product of consecutive elements:  [90, 1000]
The max product of consecutive elements:  90000

Answer 7

Taking care of the thing if there are no 1's in the array and the product coming should not be 1 in that case. Here is my code:

#include<bits/stdc++.h>
using namespace std;

int max(int x, int y)
{ return (y > x)? y : x; }
int min(int x, int y)
{ return (y < x)? y : x; }
bool search(int a[],int k,int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]==k)
        return true;
    }
    return false;
}

int maxSubArrayProduct(int a[], int size)
{
   int maxpos = 1, minneg=1, i;
   int pro_max = 1;

   for (i = 0; i < size; i++)
   {
        if(a[i]<0)
        {
            int temp=maxpos;
            maxpos=max(maxpos,minneg*a[i]);
            minneg=min(minneg,temp*a[i]);
        }
        if(a[i]==0)
        {maxpos=1;minneg=1;}
        if(a[i]>0)
        {
            maxpos=maxpos*a[i];
            minneg=min(minneg,minneg*a[i]);
        }
        if(pro_max<maxpos)
        pro_max=maxpos;
   }
   return pro_max;
}

/* Driver program to test maxSubArrayProduct */
int main()
{
   int a[] =  {-1,0,1};
   int n = sizeof(a)/sizeof(a[0]);
   int start=0,end=0;
   int max_pro = maxSubArrayProduct(a, n);
   if(max_pro==1)
   if(search(a,1,n))max_pro=1;
   else max_pro=0;
   printf("Maximum contiguous product is %d\n", max_pro);
   return 0;
}

Answer 8

Ignoring negative numbers for the moment...

Let A[i..j] mean A[i]*A[i+1]*...*A[j]

The problem is to find max(A[i..j])

Notice that A[i..j] = A[0..j] / A[0..i-1]

So if we calculate A[0..x] for all x.

We can then determine max(A[i..j]) = max(A[0..x]) / min(A[0..y])

Answer 9

Using python notations:

• compute min( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) and max( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ) in O(n)
• compute recursively the max product based on the fact that maxpro(v) = max( maxpro(v[:-1]) * max( prod( v[ 0: ] ), prod( v[ 1: ] ), ..., prod( v[ -1 ] ) ). This is O(n) too

Here is the code:

#
n = 5
vmax = 10

#
v = nr.randint( 1, vmax, n )
v *= nr.randint( 0, 2, n ) * 2 - 1
#
print v

#
prod_res = np.zeros( ( 2, n ), int )
prod_res[ 0, 0 ] = prod_res[ 1, 0 ] = v[ 0 ]
for i in xrange( 1, n ) :
    prod_res[ 0, i ] = min( v[ i ], prod_res[ 1, i-1 ] * v[ i ], prod_res[ 0, i-1 ] * v[ i ] )
    prod_res[ 1, i ] = max( v[ i ], prod_res[ 1, i-1 ] * v[ i ], prod_res[ 0, i-1 ] * v[ i ] )
#
print prod_res

#
def maxpro_naive( v ) :
    return v[ 0 ] if ( len( v ) == 1 ) else max( maxpro_naive( v[ :-1 ] ), prod_res[ 1, len(v) -1 ] )
#
print maxpro_naive( v )