Python Maximum Pairwise Product time limit exceeded 错误

Question

n = int(input())
a = [int(x) for x in input().split()]
product = 0
for i in range(n):
  for j in range(i + 1, n):
    product = max(product, a[i] * a[j])
print(product)

当我将上述代码提交给Corsera的编码判断系统时，

失败案例 #4/17:超出时间限制(使用时间:9.98/5.00，使用内存:20918272/536870912。)

已返回。我该如何更改它？

Answer 1

它在 O(n^2) 中。您可以排序 a并在a中选择两个较大的值结果为 O(n log(n))(如果列表 a 的输入值为正)。

input_list = sorted(a)
product = max(a[0]*a[1], a[-1] * a[-2]) #as suggested in comments if there is negative values