Решите задачу срочно!!! Даю 100 балов.





Задача №111176. Наибольшее произведение трех чисел
В данном списке из ≤105
n
≤
10
5
целых чисел найдите три числа,произведение которых максимально.

Решение должно иметь сложность ()
O
(
n
)
, где
n
- размер списка.

Выведите три искомых числа в любом порядке.

Примеры
входные данные
3 5 1 7 9 0 9 -3 10
выходные данные
10 9 9
входные данные
-5 -30000 -12
выходные данные
-5 -12 -30000

Решение задачи делается за O(n), если за один проход по массиву одновременно отслеживать несколько ключевых значений.

Идея

Максимальное произведение из трёх чисел может получиться в двух случаях:

1. Произведение трёх самых больших чисел

2. Произведение самого большого числа и двух самых маленьких (отрицательных), потому что:
   отрицательное × отрицательное = положительное

Значит нужно найти:

• три максимальных числа: max1 ≥ max2 ≥ max3

• два минимальных числа: min1 ≤ min2

И затем сравнить:

• P1 = max1 * max2 * max3

• P2 = max1 * min1 * min2

И выбрать большее произведение.

Как делать за O(n)

Проходим массив один раз и поддерживаем:

Три максимума:

• max1 (самое большое)

• max2 (второе)

• max3 (третье)

Два минимума:

• min1 (самое маленькое)

• min2 (второе самое маленькое)

Обновляем их на каждом шаге.

Алгоритм обновления

Для каждого числа x:

Обновляем максимумы:

• если x > max1:

  • max3 = max2

  • max2 = max1

  • max1 = x

• иначе если x > max2:

  • max3 = max2

  • max2 = x

• иначе если x > max3:

  • max3 = x

Обновляем минимумы:

• если x < min1:

  • min2 = min1

  • min1 = x

• иначе если x < min2:

  • min2 = x

Выбор ответа

После прохода:

• если max1 * max2 * max3 ≥ max1 * min1 * min2
  → выводим max1, max2, max3

• иначе
  → выводим max1, min1, min2

(порядок вывода любой)

Пример

Массив:
-5 -30000 -12

Минимумы: -30000, -12
Максимум: -5

Произведение:

• (-5) * (-30000) * (-12) = большое отрицательное? проверим:
  (-30000 * -12 = 360000), 360000 * -5 = -1800000
  Но другого варианта нет, значит берём эти три числа.

Ответ:
-5 -12 -30000

Сложность

• Время: O(n) (один проход)

• Память: O(1)

Итог

Нужно за один проход найти 3 максимума и 2 минимума, затем сравнить два варианта произведения и вывести соответствующие три числа.