Автор: С.В. Шедов

Сначала попробуем решить задачу очевидным способом, который сразу приходит на ум. Переберем все тройки чисел и выберем из них такую, которая имеет максимальное произведение.

В этом решении существуют две проблемы. Во-первых, оно успевает сработать примерно только при N<100. Нетрудно подсчитать, что количество раз, которое выполняется тело цикла (количество итераций цикла) равно N*N*N или N ³. Для подсчета времени работы программы удобно считать, что за 1 секунду выполняется порядка 1 миллиона итераций цикла (разумеется, если в теле цикла содержатся вызовы функций или другие циклы, то эта оценка неверна).

Кроме того, у решения есть еще один недостаток. Элементы последовательности по модулю могут достигать 30000 и, вообще говоря, их произведение может выйти за пределы 32-битного целого типа longint. Можно схитрить и решить эту проблему, используя, например, тип extended для переменных t и max.

Однако есть более красивое решение, которое полностью решает задачу с учетом ограничений, поставленных в задаче и при этом не прибегает ни к каких хитростям. Рассмотрим его.

В задаче нам необходимо найти такие три числа, произведение которых максимально. То есть, какие бы другие три числа мы не выбирали, их произведение будет всегда меньше или равно максимальному. Теперь давайте сообразим, какие именно числа в последовательности могут давать максимальное произведение. Первое, что приходит на ум – три максимальных числа последовательности. Для последовательностей с неотрицательными элементами это действительно так.

Рассмотрим пример:

Когда все числа в последовательности неотрицательны, то максимальное произведение дадут именно три максимальных элемента. В нашем примере это 9*6*6=324.

Остается понять, как искать три максимальных элемента. Алгоритм нахождения максимального элемента массива широко известен и не требует пояснений. Но нам надо найти не только максимальный элемент, но и «второй» и «третий» максимумы. В нашем примере первый максимум = 9, второй (следующий по значению) = 6, третий = 6. Обратите внимание, что максимумы могут совпадать по значению.

К счастью, задача поиска трех максимумов решается несложно. Пусть в переменных max1, max2, max3 хранятся первый, второй и третий максимум соответственно. Присвоим им начальные значения, равные –30000. В процессе работы программы они будут либо улучшены, либо оставлены без изменений (в случае, если последовательность состоит только из минимально возможных чисел –30000).

Воспользуемся идеей «проталкивания сверху вниз» очередного элемента в текущие три максимума. Снова обратимся к нашему примеру. Пусть мы уже просмотрели четыре элемента последовательности и правильно заполнили переменные max1, max2 и max3.

max1	Max2	max3
5	3	1

Мы считали из входного файла очередное число последовательности k=9. Сначала сравним его с переменной max1.

if k > max1 then

begin

max3 := max2;

max2 := max1;

max1 := k;

end

Поскольку 9>5, то произведем «проталкивание» нового максимума – запишем k в max1, а в max2 – старое значение max1 (ведь оно было больше или по крайней мере равно max2!). В max3 запишется старое значение max2, прежнее значение max3 при этом теряется – хранить его нет больше смысла.

k	max1	max2	max3
9	5	3	1

Таким образом, мы получим:

max1	max2	max3
9	5	3

Если окажется, что k≤max1, тогда следует его сравнить с max2.

if k > max2 then

begin

max3 := max2;

max2 := k;

end

Например, для 7 элемента нашего примера, k=6:

k	max1	Max2	max3
6	9	5	3

Мы не изменяем max1, вместо max2 записывается k, а на место max3 становится прежний max2.

В противном случае сравнивается k и max3.

if k > max3 then max3 := k;

Можно реализовывать не «проталкивание сверху вниз», а «проталкивание снизу вверх». Программная логика в этом случае претерпит лишь небольшие изменения:

if k>max3 then max3 := k;

if k>max2 then

begin

max3 := max2;

max2 := k;

end;

if k>max1 then

begin

max2 := max1;

max1 := k;

end;

Но у нас в последовательности могут быть еще и отрицательные числа! Произведение двух отрицательных чисел положительно и поэтому необходимо найти два минимальных отрицательных числа. Произведем поиск первого и второго минимума min1 и min2 в последовательности аналогичным методом.

Теперь сравним два произведения: min1*min2 и max2*max3. Нам надо выбрать максимальное из них. Очевидно, что максимальным произведением из трех элементов будет максимальный элемент последовательности max1, умноженный на максимум из min1*min2 и max2*max3.

Вспомним, что в первом решении у нас были проблемы с переполнением при перемножении трех элементов последовательности. Чтобы избежать этих проблем здесь, мы не будем непосредственно производить перемножение трех чисел, а будем сравнивать между собой min1*min2 и max2*max3.

Однако и это еще не все! Тем и замечательны олимпиадные задачи, что мы должны учитывать все возможные случаи, которые допускают ограничения на входные данные. А что будет, если все числа в последовательности отрицательные? Тогда, в случае min1*min2>max2*max3 наш алгоритм найдет далеко не максимальное произведение. Ясно, что в этом случае ответом задачи будут просто три максимальных элемента массива, так как максимальным произведением (отрицательным!) будет max1*max2*max3.

Все остальные случаи полностью покрываются нашим алгоритмом. В том числе и различные случаи с нулем. В случае последовательности из отрицательных элементов и нескольких нулей максимальное произведение будет равно 0, но 0 в этом случае в нашем алгоритме обязательно попадет в max1, а остальные два элемента значения играть не будут. Если же в последовательности есть хотя бы один положительный элемент, то max1 никогда не будет равен нулю, поэтому если нулю оказались равны max2 и max3, то при наличии отрицательных элементов максимальное произведение будет формироваться из min1, min2 и max1.

Приведем полный текст решения данной задачи на языке Pascal. Обратите внимание на то, что мы не создаем массив и не храним последовательность элементов в памяти. Поскольку задача решается в один проход по массиву, то для нашего алгоритма этого и не требуется – в каждый момент времени нам требуется знать только один текущий элемент последовательности. Мы обрабатываем его, а затем «забываем».

Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально.