Python 最大成对乘积时间限制超出错误

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的编码判断系统时，

Failed case #4/17: time limit exceeded (Time used: 9.98/5.00, memory used: 20918272/536870912.)

已被退回。我怎样才能改变它？

Answer 1

首先按降序对项目进行排序，然后将排序列表中的第一个和第二个相乘（当然如果所有的都是正的）会不会更耗时？

Answer 2

它在 O(n^2) 中。您可以在 O(n log(n)) 中排序a并选择两个较大的值a（如果列表的输入值为a正）。input_list = sorted(a)product = max(a[0]*a[1], a[-1] * a[-2]) #as suggested in comments if there is negative values