Наибольшее произведение двух чисел в списке
Дан список целых (возможны отрицательные). Верните наибольшее произведение двух различных элементов. Стремитесь к O(n) времени, O(1) памяти.
Пример: [-10, -9, 1, 2] → 90 (из -10 * -9).
def max_pair_product(nums: list[int]) -> int:
# ваш код здесьНапишите реализацию.
Ответ — max(top1 * top2, bottom1 * bottom2) — два наибольших ИЛИ два наименьших. Второй кандидат важен, потому что два больших по модулю отрицательных дают большой положительный результат. Находят два наибольших и два наименьших за один проход O(n) (или sorted за O(n log n)).
- ✗Перемножать только два наибольших, упуская два отрицательных
- ✗Соединять максимум с минимумом вместо двух краёв
- ✗Терять знаки, беря модули
- →На каком входе подход «только два наибольших» проваливается?
- →Как сделать это за один проход без сортировки?
The maximum product is either the two largest values or the two smallest (two big negatives multiply to a big positive), so compare both candidates.
def max_pair_product(nums: list[int]) -> int:
s = sorted(nums) # O(n log n); a one-pass O(n) scan also works
return max(s[-1] * s[-2], s[0] * s[1])For [-10, -9, 1, 2]: two largest give 1 * 2 = 2, but two smallest give -10 * -9 = 90, so the answer is 90. Checking only the two largest would wrongly return 2. Tracking the top-two and bottom-two values in a single linear scan achieves O(n) time, O(1) space.
