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

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

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

Задача: В данном списке из 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.
не подходит.

Новые блоги и статьи Все статьи Все блоги /
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .

@Mon4ik 1 / 1 / 0 Регистрация: 07.10.2015 Сообщений: 37

	Наибольшее произведение трех чисел 22.11.2016, 22:39. Показов 39699. Ответов 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 Сообщений: 901
	22.11.2016, 22:51
	ну смотрите: вы задачу поиска максимума можете решить? можете. бежите по списку, и присваиваете переменной максимальное значение. а теперь также ищите 3 максимальных значения. т.е. 3 вспомогательных переменных и все. вот вам и o(n). Добавлено через 6 минут п.с. не смотря на то, что в цикле получается 3 условия, o(n) сохраняется, потому что в каждой итерации верной может быть только одно: если элемент больше максимального, максимальное = элемент. иначе, если элемент больше второго максимального, то второе по максимальное = элементу. если третье меньше элемента, третье = элементу. 1

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

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

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