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

@Abblrvalg · Регистрация: 23.04.2022

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

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
 
 
def main():
  with open('input.txt', 'r') as f: #считываю строку 
    list_nums = [int(n) for n in f.readline().split()]
    nums = sorted(list_nums) #сортирую по возрастанию
    variables = []
    product = []
    for i in range(0, len(nums) - 2): #алгоритм трёх точек
        l = i + 1
        r = len(nums) - 1
        while l < r:
            product.append(nums[i] * nums[l] * nums[r]) #добавляю произведение в список
            variables.append((nums[i], nums[l], nums[r])) #добавляю числа произведения
            l += 1
            r -= 1
    ans = list(variables[product.index(max(product))]) #максимальное произведение использую как индекс нахождения чисел этого произведения в списке чисел
    s = ' '.join([str(x) for x in ans]) #преобразую в строку
    print(s)
 
if __name__ == '__main__':
    main()

мой код
Memory limit exceeded
подскажите, пожалуйста , по улучшению кода
спасибо)

Добавлено через 17 минут
...проходит 35 тестов из 57
здесь есть разбор https://www.youtube.com/live/m... are&t=2296 (38:16) - но ,типо, свой вариант прокачать)

@Ferrino · 01.06.2023, 16:37

Я так написал, привёл решение примера входа, обрабатываю все случаи (тройка положительных или есть два отрицательных или вовсе все отрицательны), жаль не нашёл тесты

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
from itertools import permutations
 
 
nums = (int(i) for i in "3 5 1 7 9 0 9 -3 10".split())
 
#with open('input.txt', 'r') as f: 
#    nums = (int(n) for n in f.readline().split())
 
max_value = float("-inf")
 
try:              
    arr = []              # если массив длиной 3-4
    for _ in range(5):
        arr.append(next(nums))
except: 
    for trio in permutations(arr, 3):
        multiply = trio[0]*trio[1]*trio[2]
        if multiply > max_value:
            max_value = multiply
            three_values = trio
    print(*three_values)
    exit()
 
 
arr.sort()              # если массив длиной 5 и более
 
min_values = [*arr[:2]] # тут будет 2 минимальных значения
max_values = [*arr[2:]] # тут будут 3 максимальных значения
 
for elem in nums:
    if elem < max(min_values):  # обновляем значения
        min_values.append(elem) # в списках, если 
        min_values.sort()       # число соответствует 
        del min_values[-1]      # условиям
        continue
 
    if elem > min(max_values):
        max_values.append(elem)
        max_values.sort()
        del max_values[0]
 
arr = max_values + min_values    # перебираю все пары 
for trio in permutations(arr, 3):
        multiply = trio[0]*trio[1]*trio[2]
        if multiply > max_value:
            max_value = multiply
            three_values = trio
print(*three_values)

по поводу вашего кода, на вход приходит большой объём данных, а строка "list_nums = [int(n) for n in f.readline().split()]"создаёт список, который занимает много памяти и python валится вместе с компьютером, следует использовать genexp а не listcomp и тогда будет работать, если ваш алгоритм поиска верный, больше ваш код не смотрел дальше.

Добавлено через 5 минут
по поводу genexp и listcomp есть хорошее видео

P.S. Если необходимо, пишите, могу расписать идею моего алгоритма решения задачи. Всего наилучшего!

@eaa · 01.06.2023, 18:09

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

сортирую по возрастанию

сортировка это уже не O(n), а O(n*log(n))

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

3 5 1 7 9 0 9 -3 10
2 минимума и максимум: -3 0 10
3 максимума: 10 9 9
очевидно что 3 максимума дадут максимальное произведение.

Добавлено через 2 минуты
3 5 1 7 -9 0 -9 -3 10
2 минимума и максимум: -9 -9 10
3 максимума: 10 7 5
тут 2 минимума и максимум дают максимальное произведение.

@s_t_r_a_j · 01.06.2023, 23:11

ну а вот так

Python
1
2
3
4
5
6
7
8
data = [3, 5, 1, 7, 9, 0, 9, -3, 10]
d = []
i = 0
while i < 3:
    d.append(max(data))
    data.remove(max(data))
    i += 1
print(d)

разумеется же, что 3 максимальных элемента дадут максимальное произведение

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

@thyrex · 01.06.2023, 23:55

s_t_r_a_j, в сообщении над Вашим приведен убедительный пример, когда работает другой набор данных

@idealist · 02.06.2023, 02:27

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
from random import randint
from math import prod
 
arr=[]
n=4
for i in range(n):
    arr.append(randint(-100, 100))
arr.sort(key=abs)
print(arr)
###########################################################
ii_neg=[]
ii_pos=[]
ii_neg_neg=[]
 
def set_ii_for(i):
    global ii_neg, ii_pos, ii_neg_neg
    sort_key=lambda i: abs(arr[i])
    if arr[i] < 0:
        ii_neg.append(i)
        ii_neg.sort(key=sort_key)
        ii_neg=ii_neg[-2:]
 
        ii_neg_neg.append(i)
        ii_neg_neg.sort(key=sort_key, reverse=True)
        ii_neg_neg=ii_neg_neg[-3:]
    else:
        ii_pos.append(i)
        ii_pos.sort(key=sort_key)
        ii_pos=ii_pos[-3:]
 
for i in range(len(arr)):
    set_ii_for(i)
 
def get_values_of_indexes(*indexes):
    return [arr[i] for i in indexes]
 
if not ii_pos:
    print(sorted(get_values_of_indexes(*ii_neg_neg), key=abs))
else:
    res=[]
    for k in range(1, len(ii_pos) + 1, 2):
        res.append(ii_neg[len(ii_neg) + k - 3:] + ii_pos[len(ii_pos) - k:])
    print(sorted(get_values_of_indexes(*max(res, key=lambda x: prod(get_values_of_indexes(*x)))), key=abs))

@idealist · 02.06.2023, 12:15

С небольшими доработками:

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
from random import randint
from math import prod
 
arr = []
n = 4
for i in range(n):
    arr.append(randint(-100, 100))
arr.sort(key = abs)
print(arr)
###########################################################
ii_neg = []
ii_pos = []
ii_neg_neg = []
 
def add_elem_and_pop_min_or_max(min_or_max, elem, arr, lenn, keyy):
    arr.append(elem)
    if len(arr) > lenn:
        arr.pop(arr.index(min_or_max(arr, key=keyy)))
 
def set_ii_for(i):
    global ii_neg, ii_pos, ii_neg_neg
    sort_key = lambda i: abs(arr[i])
    if arr[i] <= 0:
        add_elem_and_pop_min_or_max(min, i, ii_neg, 2, sort_key)
        add_elem_and_pop_min_or_max(max, i, ii_neg_neg, 3, sort_key)
    elif arr[i] >= 0:
        add_elem_and_pop_min_or_max(min, i, ii_pos, 3, sort_key)
 
for i in range(len(arr)):
    set_ii_for(i)
 
def get_sort_values_of_indexes(*indexes):
    return sorted([arr[i] for i in indexes], key=abs)
 
if not ii_pos:
    print(get_sort_values_of_indexes(*ii_neg_neg))
else:
    res = [ii_neg[len(ii_neg) + k - 3:] + ii_pos[-k:] for k in range(1, len(ii_pos) + 1, 2)]
    print(get_sort_values_of_indexes(*max(res, key=lambda x: prod(get_sort_values_of_indexes(*x)))))

Добавлено через 6 минут
Встретил в интернете статью, где перечисляются 5 способов поиска элемента в списке питона, но метод index() не упоминается!

@Ferrino · 02.06.2023, 13:22

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

С небольшими доработками:

Есть такая беда, что поток входных данных очень большой ((3≤n≤10**5)) и решение со списком занимает много памяти, что возникает ошибка меморизации, необходимо решение с использованием генератора. На таком отрезке до 10**5 может и не будет перегруза, но ошибка меморизации в коде у автора вопроса меня напрягает

@thyrex · 02.06.2023, 13:30

все бы ничего, но

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

сортировка это уже не O(n), а O(n*log(n))

@idealist · 02.06.2023, 14:23

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

Есть такая беда, что поток входных данных очень большой ((3≤n≤10**5)) и решение со списком занимает много памяти, что возникает ошибка меморизации, необходимо решение с использованием генератора. На таком отрезке до 10**5 может и не будет перегруза, но ошибка меморизации в коде у автора вопроса меня напрягает

Ну, я пока на этапе алгоритма и его тестирования. Хотел потестировать вашу программу, но не нашел куда там совать массивы. Можете такой вариант опубликовать?

@Ferrino · 02.06.2023, 16:10

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

Ну, я пока на этапе алгоритма и его тестирования. Хотел потестировать вашу программу, но не нашел куда там совать массивы

там входные данные не массив, а строка из файла, у автора в начале его кода:

Python
1
2
with open('input.txt', 'r') as f: #считываю строку 
    list_nums = [int(n) for n in f.readline().split()]

только он брал всё в список, а я беру в генератор

у меня в примере на входе строка "3 5 1 7 9 0 9 -3 10" , но она как бы и приходит из файла поэтому у меня она и расписана.

Python
1
nums = (int(i) for i in "3 5 1 7 9 0 9 -3 10".split())

@idealist · 02.06.2023, 17:03

Мой вариант с чтением из файла через генератор:

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
from math import prod
 
def add_elem_and_pop_min_or_max(min_or_max, val, ii_cur, lenn):
    ii_cur.append(val)
    if len(ii_cur) > lenn:
        ii_cur.pop(ii_cur.index(min_or_max(ii_cur, key=abs)))
 
def set_ii_for(val):
    global ii_neg, ii_pos, ii_neg_neg
    if val <= 0:
        add_elem_and_pop_min_or_max(min, val, ii_neg, 2)
        add_elem_and_pop_min_or_max(max, val, ii_neg_neg, 3)
    if val >= 0:
        add_elem_and_pop_min_or_max(min, val, ii_pos, 3)
 
with open('input.txt') as f:
    arr = (int(n) for n in f.readline().split())
ii_neg = []
ii_pos = []
ii_neg_neg = []
 
for val in arr:
    set_ii_for(val)
 
def get_sort_values_of_indexes(*indexes):
    return sorted([val for val in indexes], key=abs)
 
if not ii_pos:
    print(get_sort_values_of_indexes(*ii_neg_neg))
else:
    res = [ii_neg[len(ii_neg) + k - 3:] + ii_pos[-k:] for k in range(1, len(ii_pos) + 1, 2)]
    print(*get_sort_values_of_indexes(*max(res, key=lambda x: prod(get_sort_values_of_indexes(*x)))))

@Ferrino · 02.06.2023, 17:18

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

Мой

вот результаты наших алгоритмов, обе идеи верные:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
from itertools import permutations
from math import prod
from time import time
 
tests = ["-3 -5 1", 
         "3 5 7 1", 
         "3 5 1 7 9 0 9 -3 10", 
         "3 5 1 7 9 0 9 -3 10 -999999",
         "3 5 1 7 9 0 9 -3 10 10000",
         "3 5 1 7 9 0 9 -3 10"*100000,
         "3 5 1 7 9 0 9 -3 10"*500000]
 
 
for test in tests:
    print()
 
     #############
    ### Ferrino ###
     #############
 
    start = time()
    nums = (int(i) for i in test.split())
 
    #####with open('input.txt', 'r') as f: 
    #####    nums = (int(n) for n in f.readline().split())
 
    max_value = float("-inf")
 
    try:              
        arr = []              # если массив длиной 3-4
        for _ in range(5):
            arr.append(next(nums))
    except: 
        pass
        
    arr.sort()              # если массив длиной 5 и более
 
    min_values = [*arr[:2]] # тут будет 2 минимальных значения
    max_values = [*arr[2:]] # тут будут 3 максимальных значения
 
    for elem in nums:
        if elem < max(min_values):  # обновляем значения
            min_values.append(elem) # в списках, если 
            min_values.sort()       # число соответствует 
            del min_values[-1]      # условиям
            continue
 
        if elem > min(max_values):
            max_values.append(elem)
            max_values.sort()
            del max_values[0]
            continue
 
    arr = max_values + min_values    # перебираю все пары 
    for trio in permutations(arr, 3):
            multiply = trio[0]*trio[1]*trio[2]
            if multiply > max_value:
                max_value = multiply
                three_values = trio
    print(three_values, "Ferrino", time()-start)
 
 
 
     ##############
    ### idealist ###
     ##############
     
    start = time()
    def add_elem_and_pop_min_or_max(min_or_max, k_and_val, ii_cur, lenn):
        ii_cur.append(k_and_val)
        if len(ii_cur) > lenn:
            ii_cur.pop(ii_cur.index(min_or_max(ii_cur, key=lambda k_and_v: abs(k_and_v[1]))))
 
    def set_ii_for(k,val):
        global ii_neg, ii_pos, ii_neg_neg
        if val <= 0:
            add_elem_and_pop_min_or_max(min, (k,val), ii_neg, 2)
            add_elem_and_pop_min_or_max(max, (k,val), ii_neg_neg, 3)
        if val >= 0:
            add_elem_and_pop_min_or_max(min, (k,val), ii_pos, 3)
 
    #####with open('input.txt') as f:
    #####    arr = (int(n) for n in f.readline().split())
    arr = (int(n) for n in test.split())
 
    ii_neg = []
    ii_pos = []
    ii_neg_neg = []
 
    for i,val in enumerate(arr):
        set_ii_for(i, val)
 
    def get_sort_values_of_indexes(*indexes):
        return sorted([k_and_val[1] for k_and_val in indexes], key=abs)
 
    if not ii_pos:
        print(get_sort_values_of_indexes(*ii_neg_neg), end = " ")
        print("idealist", time()-start)
    else:
        res = [ii_neg[len(ii_neg) + k - 3:] + ii_pos[-k:] for k in range(1, len(ii_pos) + 1, 2)]
        print(get_sort_values_of_indexes(*max(res, key=lambda x: prod(get_sort_values_of_indexes(*x)))),end=" ")
        print("idealist", time()-start)

на выводе:

(1, -5, -3) Ferrino 0.0
[1, -3, -5] idealist 0.0

(5, 7, 3) Ferrino 0.0
[3, 5, 7] idealist 0.0

(9, 9, 10) Ferrino 0.0
[9, 9, 10] idealist 0.0

(10, -999999, -3) Ferrino 0.0009980201721191406
[-3, 10, -999999] idealist 0.0

(9, 10, 10000) Ferrino 0.0
[9, 10, 10000] idealist 0.0

(103, 103, 103) Ferrino 0.48720574378967285
[103, 103, 103] idealist 1.4761958122253418

(103, 103, 103) Ferrino 2.0904481410980225
[103, 103, 103] idealist 7.143882989883423

последний тест - 4_500_000 чисел (по задаче максимум 100_000), наши алгоритмы успешно справились, мы молодцы

@idealist · 02.06.2023, 17:50

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

вот результаты

Спасибо, интересно. Ну, я на скорость пока еще не оптимизировал.

@eaa · 02.06.2023, 19:36

Не по теме:

thyrex, я смотрю коды в этой теме, думаю попал в параллельную реальность.

@idealist · 03.06.2023, 19:43

Вот этот код должен поживее выполняться:

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
from math import prod
from heapq import heapify, heappush, heappushpop
 
def add_elem_and_pop(val, vv_cur, lenn):
    if len(vv_cur) < lenn:
        heappush(vv_cur, val)
    else:
        heappushpop(vv_cur, val)
 
def set_vv(val):
    global vv_neg, vv_pos, vv_neg_neg
    if val <= 0:
        add_elem_and_pop(-val, vv_neg, 2)
        add_elem_and_pop(val, vv_neg_neg, 3)
    if val >= 0:
        add_elem_and_pop(val, vv_pos, 3)
 
with open('input.txt') as f:
    arr = (int(n) for n in f.readline().split())
vv_neg = []
vv_pos = []
vv_neg_neg = []
 
for val in arr:
    set_vv(val)
 
vv_neg = [-x for x in vv_neg]
 
if not vv_pos:
    print(*sorted(vv_neg_neg, key=abs))
else:
    res = [vv_neg[len(vv_neg) + k - 3:] + vv_pos[-k:] for k in range(3 - len(vv_neg), len(vv_pos) + 1)]
    res = max(res, key=prod)
    print(*sorted(res, key=abs))

@Doule_ · 04.06.2023, 11:15

Знатоки, подскажите, будет ли этот код всегда работать корректно? (На тестах, которые были приведены выше, всё работает)

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
from functools import reduce
 
 
def find_max(arr: list[int]):
    abs_arr = list(map(abs, arr))
    mx = []
 
    for _ in range(3):
        ind = abs_arr.index(max(abs_arr))
        mx.append(arr[ind])
        arr.pop(ind)
        abs_arr.pop(ind)
 
    if reduce(lambda x, y: x * y, mx) < 0:
        abs_mx = list(map(abs, mx))
        mx.pop(abs_mx.index(min(abs_mx)))
        if all(i >= 0 for i in mx):
            mx.append(max(arr))
        else:
            mx.append(min(arr))
 
    return mx
 
 
def main():
    global tests
 
    for i in tests:
        arr = list(map(int, i.split()))
 
        if len(arr) < 3:
            raise ValueError('Not enough values')
 
        print(*find_max(arr))
 
 
tests = ["-3 -5 1",
         "3 5 7 1",
         "3 5 1 7 9 0 9 -3 10",
         "3 5 1 7 9 0 9 -3 10 -999999",
         "3 5 1 7 9 0 9 -3 10 10000",
         "3 5 1 7 9 0 9 -3 10" * 100000,
         "3 5 1 7 9 0 9 -3 10" * 500000]
 
if __name__ == '__main__':
    main()

Добавлено через 16 минут
Сам нашел ошибку. Если все значения отрицательны, то работало неверно. Теперь, вроде, всё должно работать

Python
1
2
3
4
5
6
7
8
9
10
11
    if reduce(lambda x, y: x * y, mx) < 0:
        abs_mx = list(map(abs, mx))
        if all(i >= 0 for i in mx):
            mx.pop(abs_mx.index(min(abs_mx)))
            mx.append(max(arr))
        elif all(i < 0 for i in mx):
            mx.pop(mx.index(max(mx)))
            mx.append(max(arr))
        else:
            mx.pop(abs_mx.index(min(abs_mx)))
            mx.append(min(arr))

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании 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 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	01.06.2023, 23:55
	s_t_r_a_j, в сообщении над Вашим приведен убедительный пример, когда работает другой набор данных 1

@eaa
	02.06.2023, 19:36
	Не по теме: thyrex, я смотрю коды в этой теме, думаю попал в параллельную реальность. 0