0

Нужно найти максимальное произведение двух чисел в списке. Числа могут быть и отрицательные. Код рабочий, но тестирующая программа выдаёт Time Limit Exceeded. Как можно его оптимизировать? Интересно можно ли преобразовать имеющихся 2 for в list comprehension, ибо у меня за 3 часа это сделать так и не получилось.

def composition():
    s = [int(i) for i in input().split()]
    lists = []
    total = 0
    for i in range(len(s)):
        for j in range(len(s)):
            if s[i] * s[j] > total and i != j:
                total = s[i] * s[j]
                lists.append(s[i])
                lists.append(s[j])
    a = lists[-1]
    b = lists[-2]
    if a < b:
        return a, b
    return b, a
print(*composition())
2
  • максимальное произведение двух чисел?
    – Zhihar
    24 окт 2020 в 7:02
  • Текст задачи следующий: Дан список, заполненный произвольными целыми числами. Найдите в этом списке два числа, произведение которых максимально. Выведите эти числа в порядке неубывания.
    – Krovorgen
    24 окт 2020 в 7:04

3 ответа 3

8

самый короткий код без использования каких либо библиотек :)

data = sorted([*map(int, input().split())])

print(data[0], data[1]) if data[0] * data[1] > data[-1] * data[-2] else print(data[-1], data[-2])

более короткое решение:

data = sorted([*map(int, input().split())])

print(*max(data[:2], data[-2:], key=lambda obj: obj[0] * obj[1]))
4
  • Сдача задачи 100/100 OK
    – Krovorgen
    24 окт 2020 в 7:35
  • Спасибо большое за ответы, подкоректировал для вывода в порядке возрастания и всё ок!
    – Krovorgen
    24 окт 2020 в 7:37
  • элегантное решение) 24 окт 2020 в 8:39
  • 3
    @MaxU, добавил второй вариант - еще более короткий.. и надеюсь более элегантный :)
    – Zhihar
    24 окт 2020 в 10:49
3

ну если решать совсем в лоб, вот просто в лобешник, то

data = [*map(int, input().split())]

# оцениваем только положительные числа
max1pos = max(data[0], data[1])
max2pos = min(data[0], data[1])

for value in data:
    if value <= 0:
        continue

    if value >= max1pos:
        max1pos, max2pos = value, max1pos
    elif value > max2pos:
        max2pos = value

# оцениваем только отрицательные числа числа
max1neg = min(data[0], data[1])
max2neg = max(data[0], data[1])

for value in data:
    if value > 0:
        continue

    if value <= max1neg:
        max1neg, max2neg = value, max1neg
    elif value < max2neg:
        max2neg = value

# выводим результат
print(max1pos, max2pos) if max1pos * max2pos > max1neg * max2neg else print(max1neg, max2neg)

вот так даже получше (покороче):

data = [*map(int, input().split())]

max1pos, max2pos = max(data[0], data[1]), min(data[0], data[1])
max1neg, max2neg = max2pos, max1pos

for value in data:
    if value <= 0:
        if value <= max1neg:
            max1neg, max2neg = value, max1neg
        elif value < max2neg:
            max2neg = value
    else:
        if value >= max1pos:
            max1pos, max2pos = value, max1pos
        elif value > max2pos:
            max2pos = value

# выводим результат
print(max1pos, max2pos) if max1pos * max2pos > max1neg * max2neg else print(max1neg, max2neg)
3

Предположу, что числа в последовательности являются уникальнымы. Для поиска всех возможных комбинаций неповторяющихся отлично подходит itertools.combinations. Для повторяющихся — combinations_with_replacement.

from itertools import combinations

data = map(int, input().split()))
uq_pairs = combinations(data)   # только уникальные неповторяющиеся пары

result = max(
    uq_pairs, 
    key=lambda x: x[0] * x[1],  # функция-ключ для поиска максимума
)
3
  • Наивная реализация (не Cython) — присутствует по ссылкам в ответе.
    – Tihon
    24 окт 2020 в 7:26
  • Спасибо, кое что новое узнал для себя :)
    – Krovorgen
    24 окт 2020 в 7:38
  • В встроенных модулях functools, itertools и operator — скрывается магия :)
    – Tihon
    24 окт 2020 в 7:41

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.