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

Задача, которую предлагали на собеседованиях в 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:

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

Источник: Interview Cake