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

@karslava · Регистрация: 30.01.2020

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

В данном списке из n≤10⁵ целых чисел найдите три числа,произведение которых максимально.

Решение должно иметь сложность O(n), где n - размер списка. То есть сортировку использовать нельзя.

Выведите три искомых числа в любом порядке.

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
x = list(map(int, input().split()))
 
lol = x.copy()
hah = max(lol)
lol.pop(lol.index(max(lol)))
yu = max(lol)
lol.pop(lol.index(max(lol)))
su = max(lol)
lol.pop(lol.index(max(lol)))
lol = x.copy()
y1 = min(lol)
lol.pop(lol.index(min(lol)))
y2 = min(lol)
lol = x.copy()
if max(x) > 0:
    if y1 * y2 > hah * yu:
        lol.remove(y1)
        lol.remove(y2)
        print(y1, y2, max(lol))
    else:
        lol.remove(hah)
        lol.remove(yu)
        print(hah, yu, max(lol))
else:
    print(yu, su, hah)

Вот мой код, рабочий, но не полностью. Например тесты -9 -9 9 9 не проходит, какую проверку делать, или перерешивать с помощью цикла?

@Matrix3007 · 04.08.2021, 16:05

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
maxp1=maxp2=maxo1=maxo2=0
sp=map(int, input().split())
 
for i in sp:
    a,b,c=map(abs,(maxo1,maxo2,i))
    if i>0:
        if i>maxp1:
            maxp1,maxp2,maxo1,maxo2=i,maxp1,maxp2,maxo1
        elif i>maxp2:
            maxp2,maxo1,maxo2=i,maxp2,maxo1
        elif i>a:
            maxo1,maxo2=i,maxo1
        elif i>b:
            maxo2=i
    else:
        if c>a:
            maxo1,maxo2=i,maxo1
        elif c>b:
            maxo2=i
 
res=[x for x in (maxo1,maxo2) if x>0]
if len(res)==0:
    print(maxp1,maxo1,maxo2)
else:
    print(maxp1,maxp2,res[0])

@kernel_mode · 04.08.2021, 20:25

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

Поэтому реализовать сортировку или сравнение будет наиболее правильным решением с точки зрения производительности.
Можно, конечно, использовать три цикла for внутри друг друга, перемножая все и вся, сравнивая результат с предыдущим, но это не эффективно.

@karslava · 04.08.2021, 21:08 **[ТС]**

kernel_mode, у меня нет проблем с логикой в задаче, есть с реализацией, потому как бы и спрашиваю

Добавлено через 2 минуты
Matrix3007, -1 -2 -3 -4 -5 при тесте таком получается 0 -5 -4, откуда 0?

@Gdez · 04.08.2021, 21:52

karslava,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
x = list(map(int, input().split()))
 
lol = x.copy()
 
hah = max(lol)
lol.pop(lol.index(hah))
 
yu = max(lol)
lol.pop(lol.index(yu))
 
su = max(lol)
 
lol = x.copy()
 
y1 = min(lol)
lol.pop(lol.index(min(lol)))
 
y2 = min(lol)
 
if y1 * y2 * hah  > hah * yu * su:
    print(y1, y2, hah)
else:
    print(su, yu, hah)

@karslava · 04.08.2021, 22:05 **[ТС]**

Gdez, Спасибо огромное, я убрал это из кода думая что все как в математике...

@Gdez · 04.08.2021, 22:12

karslava, По идее :

Python
1
2
3
x.sort()
y1, y2 = x[:2]
su, yu, hah = x[-3:]

@karslava · 04.08.2021, 22:18 **[ТС]**

Gdez, в условии сказано что сложность длина массива, значит sort nelzya)

@YUEN HOIFEF · 05.08.2021, 04:46

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
print( "gorgeous YUEN HOIFEF" )
 
 
 
lol = [ -20, -55, 0, 5, 20, 7, 4, 180, 19, 19, 3, 10, 2 ]
 
plusbrol = [ 0 ] * 3
minusbrol = [ 0 ] * 3
 
"""ABDxxxXXXX45557DSD__DOPDKM3$$$433"""
for c in lol :
    if c > 0 :
       if plusbrol[ 2 ] < c :
          plusbrol[ 1 ] = plusbrol[ 2 ]
          plusbrol[ 2 ] = c
       if plusbrol[ 1 ] < c and c < plusbrol[ 2 ] : plusbrol[ 1 ] = c
       if plusbrol[ 0 ] < c and c < plusbrol[ 1 ] : plusbrol[ 0 ] = c
    elif c < 0 :
       if minusbrol[ 2 ] > c :
          minusbrol[ 1 ] = minusbrol[ 2 ]
          minusbrol[ 2 ] = c
       if minusbrol[ 1 ] > c and c > minusbrol[ 2 ] : minusbrol[ 1 ] = c
       if minusbrol[ 0 ] > c and c > minusbrol[ 1 ] : minusbrol[ 0 ] = c
"""ABDxxxXXXX45557DSD__DOPDKM3$$$433--"""
 
f = -1
i = 0
while i < 3 :
   if minusbrol[ i ] >= 0 :
      if f == -1 :
         f = i
      else :
         f = -1
         break
   i+=1
 
 
if f > (-1) :
   minusbrol[ f ] = plusbrol[ 2 ]
 
n1 = 1
n2 = 1
 
for c in plusbrol :
   n1 *= c
 
for c in minusbrol :
   n2 *= c
 
if n1 > n2 : print( str(plusbrol) + "  " + str(n1)  )
else : print( str(plusbrol) + "  " + str(n1)  )

Реализовал алгоритм предложенный
kernel_mode,
Но вот много строк получилось.

@Gdez · 05.08.2021, 05:17

YUEN HOIFEF, [-55, -20, 180] 198000

@YUEN HOIFEF · 05.08.2021, 05:30

Доделывать надо..

Добавлено через 7 минут
Gdez,

Python
1
print( -55 * -20 * 180 )

@YUEN HOIFEF · 05.08.2021, 14:12

Подправил:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
print( "Long live YUEN HOIFEF" )
 
 
lol = [ -20, -55, 0, 5, 20, 7, 4, 180, 19, 19, 3, 10, 2 ]
#lol = [ -9, 9, 9 ]
 
plusbrol = [ 1 ] * 3
minusbrol = [ 1 ] * 3
 
 
"""ABDxxxXXXX45557DSD__DOPDKM3$$$433"""
for c in lol :
   if c > 0 :
      if plusbrol[ 2 ] < c :
         plusbrol[ 1 ] = plusbrol[ 2 ]
         plusbrol[ 2 ] = c
 
      elif plusbrol[ 1 ] < c :
         plusbrol[ 0 ] = plusbrol[ 1 ]
         plusbrol[ 1 ] = c
 
      elif plusbrol[ 0 ] < c : plusbrol[ 0 ] = c
   elif c < 0 :
      if minusbrol[ 2 ] > c :
         minusbrol[ 1 ] = minusbrol[ 2 ]
         minusbrol[ 2 ] = c
      if minusbrol[ 1 ] > c :
         minusbrol[ 0 ] = minusbrol[ 1 ]
         minusbrol[ 1 ] = c
      if minusbrol[ 0 ] > c  : minusbrol[ 0 ] = c
"""ABDxxxXXXX45557DSD__DOPDKM3$$$433--"""
 
f = -1
i = 0
while i < 3 :
   if minusbrol[ i ] >= 0 :
      if f == -1 :
         f = i
      else :
         f = -1
         break
   i+=1
 
 
if f > (-1) :
   minusbrol[ f ] = plusbrol[ 2 ]
 
n1 = 1
n2 = 1
 
for c in plusbrol :
   n1 *= c
 
for c in minusbrol :
   n2 *= c
 
print( lol )
if n1 > n2 : print( str(plusbrol) + " = " + str(n1) )
else : print( str(plusbrol) + " = " + str(n1) )

@karslava · 05.08.2021, 14:33 **[ТС]**

YUEN HOIFEF, ок, но зачем?...

@Matrix3007 · 05.08.2021, 18:45

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

-1 -2 -3 -4 -5 при тесте таком получается 0 -5 -4, откуда 0?

Решается добавлением одного условия

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .

@kernel_mode 70 / 47 / 16 Регистрация: 21.07.2021 Сообщений: 187
	04.08.2021, 20:25
	Наибольший результат произведения трех чисел даст произведение трех наибольших по значению чисел (одного знака), либо двух чисел с наибольшим абсолютным значением (одного знака) с одним положительным числом. Поэтому реализовать сортировку или сравнение будет наиболее правильным решением с точки зрения производительности. Можно, конечно, использовать три цикла for внутри друг друга, перемножая все и вся, сравнивая результат с предыдущим, но это не эффективно. 0

@karslava 1 / 1 / 0 Регистрация: 30.01.2020 Сообщений: 51
	04.08.2021, 21:08 [ТС]
	kernel_mode, у меня нет проблем с логикой в задаче, есть с реализацией, потому как бы и спрашиваю Добавлено через 2 минуты Matrix3007, -1 -2 -3 -4 -5 при тесте таком получается 0 -5 -4, откуда 0? 0

@karslava 1 / 1 / 0 Регистрация: 30.01.2020 Сообщений: 51
	04.08.2021, 22:05 [ТС]
	Gdez, Спасибо огромное, я убрал это из кода думая что все как в математике... 0

@karslava 1 / 1 / 0 Регистрация: 30.01.2020 Сообщений: 51
	04.08.2021, 22:18 [ТС]
	Gdez, в условии сказано что сложность длина массива, значит sort nelzya) 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.08.2021, 05:17
	YUEN HOIFEF, [-55, -20, 180] 198000 1

@karslava 1 / 1 / 0 Регистрация: 30.01.2020 Сообщений: 51
	05.08.2021, 14:33 [ТС]
	YUEN HOIFEF, ок, но зачем?... 0