Задача о максимальном произведении трех чисел массива

Задача, которую предлагали на собеседованиях в Apple: у вас есть массив с целыми числами, в том числе и отрицательными, вам нужно найти самое большое произведение 3 чисел из этого массива.

Например: у вас есть массив list_of_ints, содержащий числа -10, -10, 1, 3, 2. Функция, которая обрабатывает этот массив, должна вернуть 300, так как -10 * -10 * 3 = 300. Задание нужно выполнить максимально эффективно, не забывая про отрицательные числа.

Решение

Методов решения много, но не так просто добиться O(n) времени выполнения и O(1) затрат памяти. Для эффективного решения задачи мы создадим и будем наблюдать за состоянием следующих переменных:

• highest_product_of_three
• highest_product_of_2
• highest
• lowest_product_of_2
• lowest

Когда мы пройдемся по массиву до конца, в highest_product_of_three будет содержаться наш ответ, а остальные переменные мы используем как временный буфер. highest_product_of_2 и lowest_product_of_2 будут содержать наибольшее произведение из двух и наименьшее произведение из двух соответственно, а проходя по массиву, мы будем проверять произведение текущего числа current с этими переменными (отрицательный current с lowest_product_of_2 и положительный с highest_product_of_2). highest и lowest нам нужны для запоминания минимального и максимального чисел в массиве.

Код решения на Python:

def highest_product_of_3(list_of_ints):
    # Проверим, чтобы в массиве было 3 и больше чисел.
    if len(list_of_ints) < 3:
        raise Exception('Less than 3 items!')

    # Мы начнем с 3-его элемента массива (с индекса 2),
    # так как первые 2 элемента уже сразу пойдут
    # в highest_product_of_2 и lowest_product_of_2.
    highest = max(list_of_ints[0], list_of_ints[1])
    lowest =  min(list_of_ints[0], list_of_ints[1])
    highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
    lowest_product_of_2  = list_of_ints[0] * list_of_ints[1]

    # Также вычислим highest_product_of_three из первых 3-х элементов.
    highest_product_of_three = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]

    # Начинаем проход по массиву с индекса 2.
    for current in list_of_ints[2:]:

        # проверяем возможность увеличить highest_product_of_three
        # или оставляем его как есть.
        highest_product_of_three = max(
            highest_product_of_three,
            current * highest_product_of_2,
            current * lowest_product_of_2)

        # То же самое проверим и на максимальном произведении из двух.
        highest_product_of_2 = max(
            highest_product_of_2,
            current * highest,
            current * lowest)

        # И на минимальном произведении из двух.
        lowest_product_of_2 = min(
            lowest_product_of_2,
            current * highest,
            current * lowest)

        # Появилось ли новое максимальное число?
        highest = max(highest, current)

        # Появилось ли новое минимальное число?
        lowest = min(lowest, current)

    return highest_product_of_three

Сложность алгоритма — O(n) по времени выполнения и O(1) по памяти.

_{Источник: Interview Cake}