Python最大成对乘积代码提交Coursera判题超时如何优化修改

报错原因 #

你当前使用的是暴力枚举所有两两元素组合的解法，时间复杂度为O(n²)，当测试用例的数组长度n较大时，运算量会呈平方级增长，直接超出题目规定的时间上限。

优化思路 #

我们只需要一次遍历数组，把时间复杂度降到*O(n)*即可解决问题，注意要同时覆盖两种可能得到最大乘积的场景：

• 两个最大的正数相乘
• 两个最小的负数（绝对值最大）相乘

仅需要在一次遍历中记录数组中最大的两个值、最小的两个值，最后对比两种场景的乘积取最大值即可。

优化后代码 #

n = int(input())
arr = list(map(int, input().strip().split()))[:n]

# 初始化最大的两个值
max1 = max2 = float('-inf')
# 初始化最小的两个值
min1 = min2 = float('inf')

for num in arr:
    # 更新最大值序列
    if num > max1:
        max2 = max1
        max1 = num
    elif num > max2:
        max2 = num
    # 更新最小值序列
    if num < min1:
        min2 = min1
        min1 = num
    elif num < min2:
        min2 = num

result = max(max1 * max2, min1 * min2)
print(result)

额外注意点 #

原代码中input、print里多余的空字符串可以删除，减少不必要的输入输出开销。

内容的提问来源于stack exchange，提问作者ccs