如何在列表中找到两个元素的最大乘积？

I was trying out a problem on hackerrank contest for fun, and there came this question. I used itertools for this, here is the code:

我试图在hackerrank比赛中找到一个有趣的问题,然后出现了这个问题。我使用了itertools,这里是代码:

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)

Is their any other efficient way than this? As I am getting time out error on some test cases which I cant access (as its a small contest).

他们还有其他任何有效的方法吗?因为我在一些我无法访问的测试用例中出现错误(因为它是一个小小的竞赛)。

3 个解决方案

#1

Here is an implementation following @User_Targaryen's logic. heapq returns the 2 largest and 2 smallest numbers in the list, mul operator returns the products of these 2 pairs of numbers, and max returns the largest of these 2 products.

这是@ User_Targaryen逻辑之后的实现。 heapq返回列表中最大的2个和2个最小的数字,mul运算符返回这两对数字的乘积,而max返回这两个乘积中最大的一个。

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

#2

Iterate over the list and find the following:

迭代列表并找到以下内容:

Largest Positive number(a)

最大正数(a)

Second Largest Positive number(b)

第二大正数(b)

Largest Negative number(c)

最大负数(c)

Second Largest Negative number(d)

第二大负数(d)

Now, you will be able to figure out the maximum value upon multiplication, either a*b or c*d

现在,您将能够计算乘法时的最大值,a * b或c * d

#3

Just sort the list and select the largest of the products of the last 2 items in the list and the first 2 items in the list:

只需对列表进行排序,然后选择列表中最后2项的最大产品和列表中的前2项:

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

This is a O(n log n) solution due to the sort. Someone else suggested a heapq solution which I found to be faster for lists longer than a few thousand random integers.

由于排序,这是一个O(n log n)解决方案。其他人提出了一个heapq解决方案,我发现它对于长度超过几千个随机整数的列表更快。

#1