Наибольшее произведение трех чисел

@Mon4ik · Регистрация: 07.10.2015

Author24 — интернет-сервис помощи студентам

Задача: В данном списке из n ≤ 105 целых чисел найдите три числа,произведение которых максимально.
Решение должно иметь сложность O(n), где n - размер списка.
Выведите три искомых числа в любом порядке.
Примеры:
Ввод: 3 5 1 7 9 0 9 -3 10
Вывод: 10 9 9

Ввод: -5 -30000 -12
Вывод: -5 -12 -30000

Ввод: 1 2 3
Вывод: 3 2 1

Вопрос: как это реализовать? (использовать sort\sorted от всего массива не получается, потому что тогда программа не проходит по времени)

@minore · 22.11.2016, 22:51

ну смотрите: вы задачу поиска максимума можете решить? можете. бежите по списку, и присваиваете переменной максимальное значение. а теперь также ищите 3 максимальных значения. т.е. 3 вспомогательных переменных и все. вот вам и o(n).

Добавлено через 6 минут
п.с. не смотря на то, что в цикле получается 3 условия, o(n) сохраняется, потому что в каждой итерации верной может быть только одно: если элемент больше максимального, максимальное = элемент. иначе, если элемент больше второго максимального, то второе по максимальное = элементу. если третье меньше элемента, третье = элементу.

oldnewyear · 23.11.2016, 00:28

Сообщение от minore

п.с. не смотря на то, что в цикле получается 3 условия, o(n) сохраняется, потому что в каждой итерации верной может быть только одно: если элемент больше максимального, максимальное = элемент. иначе, если элемент больше второго максимального, то второе по максимальное = элементу. если третье меньше элемента, третье = элементу.

Можно по циклу 3 раза пройтись, все равно O(n) будет

@minore · 23.11.2016, 00:43

если по циклу пройтись 3 раза, то будет o(n^3).

oldnewyear · 23.11.2016, 03:43

Сообщение от minore

если по циклу пройтись 3 раза, то будет o(n^3).

О(n^3) будет только если пройтись по списку n^3 раз. Если пройтись 3 раза, будет O(3n) = O(n)

Добавлено через 1 час 47 минут

Python

numbers = [1,9,-10,-20,-8, 7, 14, 0, 20, 20, -20]
 
if len(numbers) < 3:
    print ('List should contain at least 3 numbers')
    exit (0)
 
nmax1 = numbers[0]
nmin1 = numbers[0]
 
for n in numbers:
    if n > nmax1: nmax1 = n
    if n < nmin1: nmin1 = n
 
numbers.remove(nmax1)
numbers.remove(nmin1)
nmax2 = numbers[0]
nmin2 = numbers[0]
 
for n in numbers:
    if n > nmax2: nmax2 = n
    if n < nmin2: nmin2 = n
 
numbers.remove(nmax2)
 
nmax3 = numbers[0]
 
for n in numbers:
    if n > nmax3: nmax3 = n
 
p1 = nmin1*nmin2*nmax1
p2 = nmax1*nmax2*nmax3
 
if p1 > p2:
    print (nmin1, nmin2, nmax1)
else:
    print (nmax1, nmax2, nmax3)

@Vigi · 23.11.2016, 07:34

Python

1	print(*sorted(map(int, input().split()))[::-1][:3])

oldnewyear · 23.11.2016, 07:47

Сообщение от Vigi

Python

1	print(*sorted(map(int, input().split()))[::-1][:3])

Сортировка списка не укладывается в требование к временной сложности O(n)

@vint-81 · 23.11.2016, 08:12

Python

numbers = [1,9,-10,-20,-8, 7, 14, 0, 20, 20, -20]
 
max_1 = max(numbers[0],numbers[1])
min_1 = min(numbers[0],numbers[1])
max_2 = numbers[0]*numbers[1]
min_2 = numbers[0]*numbers[1]
max_3 = numbers[0]* numbers[1]*numbers[2]
 
for x in numbers[2:]:
    max_3 = max(max_3, x*max_2, x*min_2)
        max_2 = max(max_2, x*max_1, x*min_1)
        min_2 = min(min_2, x*max_1, x*min_1)
        max_1 = max(max_1,x)
        min_1 = min(min_1,x)
 
print(max_3)

Добавлено через 2 минуты

Python

numbers = [1,9,-10,-20,-8, 7, 14, 0, 20, 20, -20]
 
max_1 = max(numbers[0],numbers[1])
min_1 = min(numbers[0],numbers[1])
max_2 = numbers[0]*numbers[1]
min_2 = numbers[0]*numbers[1]
max_3 = numbers[0]* numbers[1]*numbers[2]
 
for x in numbers[2:]:
        max_3 = max(max_3, x*max_2, x*min_2)
        max_2 = max(max_2, x*max_1, x*min_1)
        min_2 = min(min_2, x*max_1, x*min_1)
        max_1 = max(max_1,x)
        min_1 = min(min_1,x)
 
print(max_3)

@Mon4ik · 23.11.2016, 21:46 **[ТС]**

oldnewyear, спасибо, у вас самый понятный код) Только он не срабатывает для 2 и 3 примеров. Не нравится, что в 25 строке индекс = 0. Почему?

oldnewyear · 23.11.2016, 22:59

Сообщение от Mon4ik

oldnewyear, спасибо, у вас самый понятный код) Только он не срабатывает для 2 и 3 примеров. Не нравится, что в 25 строке индекс = 0. Почему?

Надо сделать проверку в начале - если в списке только 3 числа, вывести их и завершить программу

@Colobyte · 29.09.2017, 14:30

Достаточно найти три наибольших элемента (обзовём их m1, m2, m3) и два наименьших (n1, n2).
Тогда наибольшее произведение будет либо m1 * m2 * m3 либо m1 * n1 * n2.
Наибольшие/наименьшие элементы можно выбрать за один проход - O(n).

@bratsker · 10.01.2018, 14:15

Сообщение от Vigi

Python

1	print(*sorted(map(int, input().split()))[::-1][:3])

при данных: 1 9 -10 -20 -8 7 14 0 20 20 -20 должны получить: -20 -20 20, а сортировка выдает 20 20 14.
не подходит.

@Mon4ik 1 / 1 / 0 Регистрация: 07.10.2015 Сообщений: 37
		1
	Наибольшее произведение трех чисел 22.11.2016, 22:39. Показов 37005. Ответов 11 Метки нет (Все метки) Задача: В данном списке из n ≤ 105 целых чисел найдите три числа,произведение которых максимально. Решение должно иметь сложность O(n), где n - размер списка. Выведите три искомых числа в любом порядке. Примеры: Ввод: 3 5 1 7 9 0 9 -3 10 Вывод: 10 9 9 Ввод: -5 -30000 -12 Вывод: -5 -12 -30000 Ввод: 1 2 3 Вывод: 3 2 1 Вопрос: как это реализовать? (использовать sort\sorted от всего массива не получается, потому что тогда программа не проходит по времени) 0

@minore 370 / 133 / 44 Регистрация: 05.02.2015 Сообщений: 897
	22.11.2016, 22:51	2
	ну смотрите: вы задачу поиска максимума можете решить? можете. бежите по списку, и присваиваете переменной максимальное значение. а теперь также ищите 3 максимальных значения. т.е. 3 вспомогательных переменных и все. вот вам и o(n). Добавлено через 6 минут п.с. не смотря на то, что в цикле получается 3 условия, o(n) сохраняется, потому что в каждой итерации верной может быть только одно: если элемент больше максимального, максимальное = элемент. иначе, если элемент больше второго максимального, то второе по максимальное = элементу. если третье меньше элемента, третье = элементу. 1

oldnewyear 440 / 432 / 159 Регистрация: 21.05.2016 Сообщений: 1,338
	23.11.2016, 00:28	3
	Сообщение от minore п.с. не смотря на то, что в цикле получается 3 условия, o(n) сохраняется, потому что в каждой итерации верной может быть только одно: если элемент больше максимального, максимальное = элемент. иначе, если элемент больше второго максимального, то второе по максимальное = элементу. если третье меньше элемента, третье = элементу. Можно по циклу 3 раза пройтись, все равно O(n) будет 0

@minore 370 / 133 / 44 Регистрация: 05.02.2015 Сообщений: 897
	23.11.2016, 00:43	4
	если по циклу пройтись 3 раза, то будет o(n^3). 0

@Mon4ik 1 / 1 / 0 Регистрация: 07.10.2015 Сообщений: 37
	23.11.2016, 21:46 [ТС]	9
	oldnewyear, спасибо, у вас самый понятный код) Только он не срабатывает для 2 и 3 примеров. Не нравится, что в 25 строке индекс = 0. Почему? 0

oldnewyear 440 / 432 / 159 Регистрация: 21.05.2016 Сообщений: 1,338
	23.11.2016, 22:59	10
	Сообщение от Mon4ik oldnewyear, спасибо, у вас самый понятный код) Только он не срабатывает для 2 и 3 примеров. Не нравится, что в 25 строке индекс = 0. Почему? Надо сделать проверку в начале - если в списке только 3 числа, вывести их и завершить программу 0

@Colobyte 0 / 0 / 0 Регистрация: 29.09.2017 Сообщений: 1
	29.09.2017, 14:30	11
	Достаточно найти три наибольших элемента (обзовём их m1, m2, m3) и два наименьших (n1, n2). Тогда наибольшее произведение будет либо m1 * m2 * m3 либо m1 * n1 * n2. Наибольшие/наименьшие элементы можно выбрать за один проход - O(n). 0

	10.01.2018, 14:15