Jak znaleźć maksymalny iloczyn dwóch elementów na liście?

Question

Próbowałem rozwiązać problem hakerów w konkursie na zabawę i pojawiło się to pytanie. użyłem itertools do tego, oto kod:

import itertools 

l = [] 

for _ in range(int(input())): 
    l.append(int(input())) 


max = l[0] * l[len(l)-1] 

for a,b in itertools.combinations(l,2): 
    if max < (a*b): 
     max = (a*b) 
print(max) 

jest ich każdy inny skuteczny sposób, niż to? Ponieważ otrzymuję błąd przekroczenia czasu w niektórych przypadkach testowych, do których nie mam dostępu (jako mały konkurs).

Answer 1

Oto implementacja następującej logiki @ User_Targaryen. heapq zwraca 2 największe i 2 najmniejsze liczby na liście, mul operator zwraca produkty tych dwóch par liczb, a max zwraca największy z tych 2 produktów.

>>> import heapq 
>>> from operator import mul 
>>> l = [2,40,600,3,-89,-899] 
>>> max(mul(*heapq.nsmallest(2,l)),mul(*heapq.nlargest(2,l))) 
80011 
# -899*-89 = 80011 

Answer 2

iteracyjne nad listy i znaleźć następujące:

największą liczbę Pozytywny (a)

drugim co do wielkości liczbę dodatnią (b)

największa liczba ujemna (c)

drugim największym Numer ujemny (d)

Teraz będziesz w stanie określić maksymalną wartość po pomnożeniu, albo a*b lub c*d

Answer 3

Wystarczy posortować listę i wybrać największy z produktów ostatnie 2 pozycje na liście i pierwsze 2 pozycje w liście:

from operator import mul 

numbers = [10, 20, 1, -11, 100, -12] 
l = sorted(numbers) # or sort in place with numbers.sort() if you don't mind mutating the list 
max_product = max(mul(*l[:2]), mul(*l[-2:])) 

Jest to O (n log n) rozwiązanie ze względu na rodzaj. Ktoś inny zasugerował rozwiązanie heapq, które okazało się szybsze w przypadku list dłuższych niż kilka tysięcy losowych liczb całkowitych.