Привет, Хабр! Сегодня разберём простую на первый взгляд, но очень показательную задачку: найти максимальное произведение двух чисел в массиве целых чисел.
На собеседованиях, в олимпиадах или даже в реальных задачах часто возникают простые на вид задачи, за которыми скрывается важный урок: правильный выбор алгоритма решает всё.
Казалось бы — что сложного скрывает поставленная задача о нахождении максимального произведения двух чисел? Но в зависимости от подхода решение может работать за O(n^2), O(n log n) или O(n).
С этой задачей я столкнулся на своём первом собеседовании и предложил не самое оптимальное решение.
В этой статье мы разберём три разных решения — от самого очевидного до оптимального, — сравним их по времени, памяти и читаемости, и увидим, как небольшая алгоритмическая хитрость позволяет ускорить код в десятки и сотни раз на реальных данных.
Постановка задачи
Дан массив целых чисел (может содержать положительные, отрицательные и нули, количество элементов не менее 1). Нужно найти максимальное возможное произведение двух различных элементов (обычно подразумевается, что индексы разные, но значения могут совпадать).
Базовое решение или как делать не надо (O(n²))
Начнём с самого прямолинейного подхода: проверим все возможные пары элементов и выберем ту, чьё произведение максимально.
Почему это работает? Потому что мы не упускаем ни одного кандидата. Даже если в массиве спрятаны два огромных по модулю отрицательных числа, мы их обязательно рассмотрим.
Как именно перебирать пары?
Чтобы не дублировать комбинации (например, 
и 
), будем перебирать только пары с 
:
идёт от 
до 
идёт от 
до 
Так мы рассмотрим ровно 
уникальных пар — это и есть квадратичная сложность или 
.
✅ Преимущества
Простота
Надёжность: не зависит от знаков, нулей, порядка — работает всегда.
Лёгкость тестирования: легко проверить на маленьких примерах вручную.
❌ Недостатки
Скорость: при n =
— уже ~
миллионов операций, исполнение которых может занять секунды. При n = 
— ~
миллиардов пар, задача выйдет за пределы Time Limit на большинстве платформ.Не масштабируется: даже если процессор станет в 10 раз быстрее — вы выиграете лишь в константе, а не в асимптотике.
Реализация на Python под катом
def max_product(arr): n = len(arr) if n < 2: return -1 max_prod = arr[0] * arr[1] # либо max_prod = arr[0] - по сути, вкусовщина for i in range(n): for j in range(i + 1, n): product = arr[i] * arr[j] if product > max_prod: max_prod = product return max_prod
Компромиссное решение (O(n log n))
Перебор всех пар - это решение слишком «в лоб», давайте подумаем: где вообще может лежать ответ?
Заметим важную вещь: Максимальное произведение двух чисел в массиве — это
либо произведение двух самых больших чисел
либо произведение двух самых маленьких (т.е. самых отрицательных) чисел
Следовательно, нам не нужно проверять все пары — достаточно рассмотреть только две кандидатные пары: 2 максимальных числа, либо 2 минимальных числа, и выбрать максимальное из их произведений.
Такое умозаключение наталкивает нас на идею сортировки массива и рассмотрении крайних 2 чисел с каждого конца. Сортировка выполняется за O(n log n), рассмотрение двух произведений - O(1), поэтому итоговая сложность алгоритма будет O(n log n)
✅ Преимущества
Очень легко понять и написать — идеально для собеседования.
Работает быстро даже для миллионов объектов.
Минимум логики — всего два сравнения после сортировки.
❌ Недостатки
Сложность O(n log n) — проигрывает линейному решению на больших данных.
Изменяет исходный массив
Реализация на Python под катом
def max_product(arr): if len(arr) < 2: return -1 arr.sort() # Два кандидата: product_of_largest = arr[-1] * arr[-2] # самые большие product_of_smallest = arr[0] * arr[1] # самые маленькие return max(product_of_largest, product_of_smallest)
Оптимальное решение (O(n))
Если мы уже поняли, что максимальное произведение — это максимум из двух кандидатов:
два самых больших числа,
два самых маленьких числа,
то зачем вообще сортировать весь массив? Ведь нам нужны только четыре числа: два максимума и два минимума.
Их можно найти за один проход, не трогая остальные элементы.
Это классический приём: поддерживать текущие экстремумы, обновляя их при просмотре каждого элемента «на лету».
Идея алгоритма
Будем отслеживать:
max1, max2 — два наибольших числа (max1 ≥ max2)
min1, min2 — два наименьших числа (min1 ≤ min2)
Проходим по массиву один раз. Для каждого элемента x:
-
Если x > max1 → max2 = max1, max1 = x
Иначе если x > max2 → max2 = x
-
Если x < min1 → min2 = min1, min1 = x
Иначе если x < min2 → min2 = x
В конце возвращаем max(max1 max2, min1 min2).
✅ Преимущества
Оптимальная временная сложность: O(n) — один проход.
Постоянная память: O(1) — только четыре переменные.
Не изменяет исходный массив — безопасен для дальнейшего использования.
Масштабируется: работает быстро даже для миллиарда объектов.
Реализация на Python под катом
def max_product_linear(arr): if len(arr) < 2: return -1 # Инициализируем экстремумы первыми двумя элементами if arr[0] > arr[1]: max1, max2 = arr[0], arr[1] min1, min2 = arr[1], arr[0] else: max1, max2 = arr[1], arr[0] min1, min2 = arr[0], arr[1] # Проходим по оставшимся элементам for i in range(2, len(arr)): x = arr[i] # Обновляем максимумы if x > max1: max2 = max1 max1 = x elif x > max2: max2 = x # Обновляем минимумы if x < min1: min2 = min1 min1 = x elif x < min2: min2 = x return max(max1 * max2, min1 * min2)
Это решение демонстрирует важный принцип:
Не нужно сортировать, если нужны только экстремумы.
Именно такие «мелкие оптимизации» часто отличают хорошего разработчика — того, кто не просто решает задачу, а думает о ресурсах.
P.S.
Почему так важно всегда помнить про сложность даже простого алгоритма?
На этом графике изображены сложности представленных решений, а конкретно, рост времени выполнения задачи в зависимости от размера входного массива. Первое решение сразу выбивается из колеи, говоря нам о том, что его лучше не использовать на практике.
Если рассматривать оставшиеся 2 решения, то, казалось бы, графики времени выполнения «почти совпадают», но нельзя не принимать во внимание тот факт, что в большинстве реальных задач размеры входных данных куда больше 20, чем ограничивается ось абсцисс на графике. Давайте будем реалистами и возьмём массив размера хоть сколько‑то приближенного к возможной реальной задачи:
Вы разрабатываете систему оповещения для умного дома. У вас есть данные за месяц наблюдений с интервалом в 5 минут — это более 8000 измерений отклонений температуры от нормы (например, −3°, +5°, −7° и т.д.). Чтобы оценить риск термического стресса для оборудования, инженеры предложили метрику: «наибольшее возможное совместное отклонение» — то есть максимальное произведение двух отклонений. Почему? Потому что два сильных отрицательных скачка (например, −8 и −6) дают положительный вклад в износ системы, как и два сильных положительных (+7 и +5).
Думаю, комментарии в пользу выбора третьего решения с линейной сложностью излишни?
Комментарии (27)
Pusk1
13.02.2026 11:36Я даже не подумал, что можно перебирать все возможные пары или сортировать массивы. Давайте что-нибудь более элегантное.
С обработкой строк 1000+ таких примеров.
Akina
13.02.2026 11:36-
Если x > max1 → max2 = max1, max1 = x
Иначе если x > max2 → max2 = x
Чтобы алгоритм работал, в паре max1, max2 необходимо поддерживать условие max2 >= max1 после каждого переприсвоения, тогда как у вас этот момент отмечен только в самом начале описания алгоритма, а не в описании блока перебора. А в нижеприведённом коде такая сортировка выполняется именно в процессе перебора, к тому же ну совершенно неявно. Впрочем, тому, кто захочет разобраться, это даже полезно..
tolich_the_shadow
13.02.2026 11:36Наоборот, max1>=max2: max1 -- максимальное значение, max2 -- второе максимальное.
-
lightln2
13.02.2026 11:36Если писать на питоне, то я бы использовал всю его мощь для таких задач. Ваше решение можно сократить более, чем в два раза и, мне кажется, в таком коде сложнее ошибиться (что особенно важно, если эта задача с собеседования):
def max_product_linear(arr): n = len(arr) if n < 2: return None max1 = max(range(n), key=lambda i: arr[i]) max2 = max(range(n), key=lambda i: arr[i] if i != max1 else -math.inf) min1 = min(range(n), key=lambda i: arr[i]) min2 = min(range(n), key=lambda i: arr[i] if i != min1 else math.inf) return max(arr[max1]*arr[max2], arr[min1]*arr[min2])
alex_tulski
13.02.2026 11:36То есть O(n) вы превратили в O(4n), создавая по новому итератору на каждый поиск ради синтаксического сахара.
lightln2
13.02.2026 11:36O(4n) - это тот же O(n). Нафига бороться за константу в коде на питоне? Тогда уж надо на c++ писать.
alex_tulski
13.02.2026 11:36Я не спорю, что асимптотика остаётся O(n). Но если мы обсуждаем оптимальные алгоритмы, то сознательно добавлять лишние полные проходы по данным — странно. Это не n², но это всё равно ухудшение константы, которое в реальном коде иногда выливается в заметную разницу.
Плюс это не выглядит как выигрыш в читаемости. Конструкция с
key=lambdaи костылём черезmath.infдобавляет скрытую логику и хуже читается, чем один явный проход с понятными инвариантами. Хотя может это моя деформация.И да, «мощь языка» имеет обратную сторону — на нём очень легко писать неоптимальные вещи, которые выглядят лаконично, что вы выше и продемонстрировали. Настоящая мощь — это когда код одновременно читаемый и не делает лишней работы.
Если бы это давало и читаемость, и скорость — ок. Но повышения скорости тут нет, а повышение читаемости сомнительно.
lightln2
13.02.2026 11:36что вы понимаете под оптимальными алгоритмами?
обычно это означает "асимптотически оптимальные", но вы имеете в виду, видимо, абсолютное время? тогда перепишите код на c++ и скомпилируйте с -Ofast -march=native и это будет оптимально, так как упрется в пропускную способность памяти (и то не на всех архитектурах, так как иногда в один поток невозможно нагрузить память, надо будет параллелить).
Даже если вы имеете в виду абсолютное время на питоне, то наверняка какой-нибудь numpy.partition будет быстрее, так как выполняется нативно на numpy-массивах. Ну и даже для вашего алгоритма наверняка распараллеливание на несколько потоков его ускорит.повышение читаемости сомнительно
это стандартный шаблон argmax (одна из полезных функций, отсутствующих в питоне, но присутствующих, например, в numpy) - он обычно легко распознается при чтении, если вам знаком
edwardoid
13.02.2026 11:36Вы действительно не понимаете, что он имеет ввиду под "оптимальные алгоритмы"?
winkyBrain
13.02.2026 11:36вот я тоже удивился самому факту существования этой темы, потому что обычно питонистам насрать на оптимизацию, DRY и прочее)
wataru
13.02.2026 11:36Ну нет, тут замедление не в 4 раза алгоритмически. Максимум в 2. Ибо у вас тоже 4 сравнения в теле цикла. Но зато вы экономите на единой проверке счетчика итераций, а тут 4 цикла каждый отдельно проверяют i. И некоторые проверки у вас иногда пропускаются.
Оригинальный подход был бы быстрее на языке более низкого уровня, там бы один проход читал бы из памяти лишь один раз, что на больших массивах сильно быстрее чтения 4 раза. Но в питоне все эти оптимизации весьма условные, все переменные - огромные объекты, а ручная итерация по массиву работает вообще страшно медленно по сравнению со встроенными функциями. Так что это еще большой вопрос, чей код на самом деле быстрее. Надо бенчмарки гонять.
И вообще O(4n) - то же самое O(n).
В контексте статьи для обучения и интервью вот эти вот 4 отдельных цикла на порядки читабельнее и поэтому лучше.
alex_tulski
13.02.2026 11:36Я не поленился и побенчил. Вариант с лямбдами медленнее в 3 раза.
------------------------------------------------------------------------------------------------------------- benchmark: 12 tests -------------------------------------------------------------------------------------------------------------- Name (time in ns) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ test_linear[10] 708.0380 (1.0) 57,209.0503 (1.02) 835.6700 (1.0) 295.8940 (1.0) 833.0680 (1.0) 1.1642 (1.0) 354;43287 1,196,644.5862 (1.0) 142861 1 test_linear2[10] 2,583.0232 (3.65) 55,833.9525 (1.0) 2,728.8291 (3.27) 399.6901 (1.35) 2,708.0532 (3.25) 1.1642 (1.0) 294;50327 366,457.5425 (0.31) 116509 1 test_linear[100] 6,582.8208 (9.30) 97,834.0395 (1.75) 6,750.1172 (8.08) 746.9517 (2.52) 6,708.0837 (8.05) 41.9095 (36.00) 712;11586 148,145.5749 (0.12) 129734 1 test_linear2[100] 18,165.9125 (25.66) 61,791.8558 (1.11) 18,398.7960 (22.02) 924.1897 (3.12) 18,291.8739 (21.96) 83.1205 (71.40) 1113;4551 54,351.3825 (0.05) 50850 1 test_linear[1000] 67,624.9620 (95.51) 179,792.0559 (3.22) 68,376.8114 (81.82) 2,290.5980 (7.74) 67,957.9098 (81.58) 166.0082 (142.60) 724;1534 14,624.8411 (0.01) 14261 1 test_linear2[1000] 200,291.8627 (282.88) 309,707.8297 (5.55) 202,454.4575 (242.27) 5,584.4435 (18.87) 200,666.0216 (240.88) 1,750.0133 (>1000.0) 325;564 4,939.3825 (0.00) 4497 1 test_linear[10000] 682,916.9579 (964.52) 791,667.0293 (14.18) 691,476.7826 (827.45) 8,098.1468 (27.37) 689,707.9293 (827.91) 3,542.0526 (>1000.0) 117;182 1,446.1802 (0.00) 1442 1 test_linear2[10000] 2,076,457.9531 (>1000.0) 2,245,165.8733 (40.21) 2,090,560.7943 (>1000.0) 19,249.7314 (65.06) 2,084,770.4727 (>1000.0) 11,041.0620 (>1000.0) 29;29 478.3405 (0.00) 434 1 test_linear[100000] 6,895,666.0107 (>1000.0) 7,726,832.9915 (138.39) 6,937,461.8904 (>1000.0) 80,379.9075 (271.65) 6,919,166.4224 (>1000.0) 24,874.9275 (>1000.0) 11;16 144.1449 (0.00) 142 1 test_linear2[100000] 20,933,165.9134 (>1000.0) 21,397,583.1866 (383.24) 21,026,074.6729 (>1000.0) 100,371.3917 (339.21) 20,985,625.4514 (>1000.0) 73,229.5448 (>1000.0) 7;6 47.5600 (0.00) 48 1 test_linear[1000000] 69,027,584.0461 (>1000.0) 69,449,540.9261 (>1000.0) 69,141,688.9119 (>1000.0) 132,736.1878 (448.59) 69,087,291.8349 (>1000.0) 164,583.9075 (>1000.0) 2;0 14.4631 (0.00) 15 1 test_linear2[1000000] 209,953,666.1990 (>1000.0) 210,920,625.1334 (>1000.0) 210,415,533.2316 (>1000.0) 376,636.6391 (>1000.0) 210,339,416.9826 (>1000.0) 564,583.2280 (>1000.0) 2;0 4.7525 (0.00) 5 1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Код бенчмарка
import math import random import pytest def max_product_linear(arr): if len(arr) < 2: return -1 # Инициализируем экстремумы первыми двумя элементами if arr[0] > arr[1]: max1, max2 = arr[0], arr[1] min1, min2 = arr[1], arr[0] else: max1, max2 = arr[1], arr[0] min1, min2 = arr[0], arr[1] # Проходим по оставшимся элементам for i in range(2, len(arr)): x = arr[i] # Обновляем максимумы if x > max1: max2 = max1 max1 = x elif x > max2: max2 = x # Обновляем минимумы if x < min1: min2 = min1 min1 = x elif x < min2: min2 = x return max(max1 * max2, min1 * min2) def max_product_linear_2(arr): n = len(arr) if n < 2: return None max1 = max(range(n), key=lambda i: arr[i]) max2 = max(range(n), key=lambda i: arr[i] if i != max1 else -math.inf) min1 = min(range(n), key=lambda i: arr[i]) min2 = min(range(n), key=lambda i: arr[i] if i != min1 else math.inf) return max(arr[max1]*arr[max2], arr[min1]*arr[min2]) @pytest.fixture(scope="session") def rng(): return random.Random(123456) @pytest.mark.parametrize("n", [10, 100, 1_000, 10_000, 100_000, 1_000_000]) def test_linear(benchmark, rng, n): arr = [rng.randint(-10**6, 10**6) for _ in range(n)] benchmark(max_product_linear, arr) @pytest.mark.parametrize("n", [10, 100, 1_000, 10_000, 100_000, 1_000_000]) def test_linear2(benchmark, rng, n): arr = [rng.randint(-10**6, 10**6) for _ in range(n)] benchmark(max_product_linear_2, arr)wataru
13.02.2026 11:36Спасибо. Значит лямбды добавляют накладных расходов. Но все-равно, вы утверждали про 4 раза, а тут 3.
Все равно, мне переписанный код кажется более полезным. Он проще и понятнее. На интервью его проще написать без ошибок, ни один адекватный интервьювер прикапываться к константе не будет. Людям, обучающимся решать задачи, он тоже более понятен и к нему проще прийти. На практике же, если вам важно ускорение этого кода в 3 раза, вы перепишите его с numpy (что с раздельными 4-мя циклами проще, чем с одним) и получите ускорение в несколько десятков раз.
edwardoid
13.02.2026 11:36Да хоть 3, а не 3. По сути просто из желания показать какой синтаксический сахар есть в Питере, человек взял простое и быстрое решение реализовал так, что начали рождаться вопросы, а действительно ли это оптимально. Иногда лучше сделать просто, без заигрываний.
wataru
13.02.2026 11:36Нет, там желание сделать более понятный код. Можно хоть 4 цикла написать, хоть 4 min/index, хоть с лямбдами. Оно понятнее, не надо в голове держать инварианты max1 > max2 и думать, все ли варианты покрыты, или нет. Это более естественный перевод с человеческого "найти минимальный и второй минимальный элемент". Сразу явно видно, что вот минимальный, а вот минимальный из оставшихся.
Вопросы там - к микрооптимизациям только. Их новички не задают и не понимают. И практической ценности они для интервью или соревнований не несут никакой. Любой линейный алгоритм обычно работает достаточно быстро.
arseniy-t
13.02.2026 11:36И все-таки, самый быстрый вариант — без циклов ))
def max_product_linear_3(arr): if len(arr) < 2: return -1 max1 = max(arr) i = arr.index(max1) arr[i] = -math.inf max2 = max(arr) arr[i] = max1 min1 = min(arr) i = arr.index(min1) arr[i] = math.inf min2 = min(arr) arr[i] = min1 return max(max1 * max2, min1 * min2)
yaroslavp
13.02.2026 11:36А min и max наверное по волшебству отдают нужное значение, как и функция index, точно не используя циклы под капотом?
Artem_Omny
13.02.2026 11:36Задача сложнее - это найти в реальном мире где это вообще можно использовать.
lightln2
13.02.2026 11:36Это, наверно, был риторический вопрос, но я попробую ответить.
Конкретно эта задача, может, и не имеет практического значения, но она является упражнением на поиск второго маскимума(минимума).
Это частный случай поиска k-го максимума (или первых k максимумов). Практическое значение - Вас с помощью этой задачи подводят к алгоритму quick-select (используется много где, например, в статистике для вычисления медианы/перцентилей)
Второе применение - поиск второго максимума/минимума в более сложных объектах. Классическая задача - поиск второго оптимального пути в ациклических направленных графах. Практическое применение - быстрое вычисление оптимальной траектории в вашей сети, если одно из ее ребер удалить (то есть, нарушилась связность между двумя узлами в сети).
A1ternative
13.02.2026 11:36Все классно, но хоть бы ответ ии не копировали точь-в-точь. Начали про вопрос с собеседования, закончили сгенерированной выкладкой.
wataru
А вот это бы хорошо доказать. На первый взгляд это не очевидно. При чем, раз уж вы тут людей учите, надо привести рассуждения, как до этого додуматься вообще.
Akina
Это несложно. Просто надо по отдельности рассматривать варианты, что среди набора этих 4 элементов имеется то или иное количество положительных, отрицательных и нулевых элементов.
wataru
Тем более, это должно быть в статье.
its_fire_fire_fun_fun_fun
Извините, это любому 5-7 класснику очевидно с базовыми склонностями к информатике. Если к такому на Хабре нужно прилагать доказательство, ресурс можно закрывать.
wataru
Во-первых, вы переоцениваете 5-7 классников. И вообще людей. Если бы это было так очевидно, это не было бы задачей для собеседований.
Во-вторых, я не просил строгое формальное доказательство, достаточно было бы какого-то наброска рассуждений.
В-третьих, для кого, по вашему, эта статья? Она как раз "для самых маленьких", людей только учащихся решать задачи. Для всех остальных вся статья тривиальна и не нужна. А вот для этих начинающих это тем более не очевидно.