Cách tìm sản phẩm tối đa của hai yếu tố trong danh sách?

Question

Tôi đã thử một vấn đề về cuộc thi hackerrank để giải trí và có câu hỏi này. Tôi đã sử dụng itertools cho mục đích này, đây là mã:

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) 

Có cách nào khác hiệu quả hơn này không? Khi tôi nhận được lỗi thời gian trên một số trường hợp thử nghiệm mà tôi không thể truy cập (như một cuộc thi nhỏ của nó).

Answer 1

Dưới đây là triển khai theo logic @ User_Targaryen. heapq trả về 2 số lớn nhất và 2 số nhỏ nhất trong danh sách, mul operator trả về các sản phẩm của 2 cặp số này và max trả về lớn nhất trong số 2 sản phẩm này.

>>> 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

lặp trên danh sách và tìm thấy những điều sau đây:

lớn nhất số dương (a)

lớn thứ hai số dương (b)

lớn nhất số âm (c)

lớn thứ hai Số âm (d)

Bây giờ, bạn sẽ có thể tìm ra giá trị lớn nhất khi nhân, a*b hoặc c*d

Answer 3

Chỉ cần sắp xếp danh sách và chọn lớn nhất trong số các sản phẩm của 2 mục cuối cùng trong danh sách và 2 mục đầu tiên trong danh sách:

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:])) 

Đây là một O (n log n) giải pháp do sắp xếp. Một người khác đã đề xuất giải pháp heapq mà tôi thấy nhanh hơn đối với danh sách dài hơn vài nghìn số nguyên ngẫu nhiên.