Finding highest product of three numbers

Question

Given an array of ints, arrayofints, find the highest product, Highestproduct, you can get from three of the integers. The input array of ints will always have at least three integers.

So I've popped three numbers from arrayofints and stuck them in highestproduct:

Highestproduct = arrayofints[:2]
for item in arrayofints[3:]:
    If min(Highestproduct) < item:
        Highestproduct[highestproduct.index(min(Highestproduct))] = item

If min of highestproduct less than item: Replace the lowest number with the current number.

This would end up with highest product, but apparently there is a better solution. What's wrong with my approach? Would my solution be O(n)?

Answer 1

Keep track of the two minimal elements and three maximal elements, the answer should be min1 * min2 * max1 or max1 * max2 * max3.

To get the maximum product of 3 ints we have to choose 3 maximum elements. However there is a catch that we can substitute 2 of the smallest of 3 max elements with the 2 min ints. If both smallest ints are negative their product is positive so min1 * min2 might be bigger than max2 * max3 (where max2 and max3 are 2 of the smallest of 3 max elements from the array).

This runs in O(n) time.

Answer 2

There are some catches on this problem, in a list involving both positive and negative int, the largest combination could be the smallest negative, second smallest negative value,largest positive value or largest positive value, second largest positive value and third largest value;

For example, a list of -5,-1,1,2,3 should return 15, but when there are only negative values in the list, this does Not work, instead of picking the smallest negative integers, the larges combination is actually the three largest negative values, for example: -5,-4,-3,-2,-1 should return -6. the easy way to code this would be just store the three largest positive values(consider 0 as positive),

Three smallest negative values and three largest negative values as we going through the array, then we try all the combinations of these nine numbers and get the max. this only takes O(n) time and O(1) space.

Answer 3

Here is a C++ implementation of the program with the running time of O(N):

#define size 5
int A[size] = {5,4,5,10,-6};

int highest_product_of_3()
{
    int highest = max(A[0],A[1]);
    int lowest = min(A[0],A[1]);

    int highestProductOf2 = A[0]*A[1];
    int lowestProductOf2 = A[0]*A[1];

    int highestProductOf3 = A[0]*A[1]*A[2];

    for (int i=2;i<size;i++)
    {
        int current = A[i];

        // Max of 3 values:
        //                  highest_product_of_3            OR
        //                  current*highestProductOf2       OR
        //                  current*lowestProductOf2

        highestProductOf3 = max(max(highestProductOf3, current*highestProductOf2),
                                current*lowestProductOf2);

        highestProductOf2 = max(max(highestProductOf2, current*highest),
                                current*lowest);

        lowestProductOf2 = min(min(lowestProductOf2, current*highest),
                                current*lowest);

        highest = max(highest, current);        // update highest

        lowest = min(lowest, current);          // update lowest
    }


    return highestProductOf3;
}

Answer 4

If you sort arrayofints first, the worst case running time is O(n log n) instead of O(n) (i.e. not quite as fast). But the code is really short. And what's a little log n between friends anyway?

def highest_product(list_of_ints):
    if len(list_of_ints) < 3:
        return None
    sorted_ints = sorted(list_of_ints)
    return max(sorted_ints[0] * sorted_ints[1] * sorted_ints[-1], sorted_ints[-3] * sorted_ints[-2] * sorted_ints[-1])

(To be clear, sorting removes the need to explicitly keep track of the three highest numbers, and the three lowest -- these are sort-like operations but are cheaper than sorting the entire list.)

Answer 5

This method basically works for any number of elements let alone 3. The idea is to sort the array first and then take the product of last and second last elements. This can be implemented in python as:

def pr(arr, n):
    n = len(arr)
    arr.sort()
    a = {}

    r = arr[n-1]
    s = arr[n-2]
    return {r, s}

arr = [1, 4, 3, 6, 7, 0]
q = pr(arr, 6)
print(q)

This prints out the set of elements whose product is the highest.