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

Question

为了好玩，我在 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)

他们还有比这更有效的方法吗？因为我在一些我无法访问的测试用例上遇到超时错误（因为这是一场小型比赛）。

Answer 1

遍历列表并找到以下内容：

最大正数(a)

第二大正数(b)

最大负数(c)

第二大负数(d)

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

Answer 2

这是遵循@User_Targaryen逻辑的实现。 heapq returns the 2 largest and 2 smallest numbers in the list, mul operatorreturns这2对数的乘积，maxreturns这2对数中最大的

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

只需对列表进行排序，select列表中最后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:]))

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

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

How to find the maximum product of two elements in a list?

python

itertools

python-2.7

python-3.x