Search code examples
pythonpython-3.xalgorithmlimit

python maximum Pairwise Product time limit error

n = int(input(" "))

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

a = arr[0];
b = arr[1];

for i in range (0, n):
    for j in range (i+1, n):
        if(arr[i] * arr[j] > a * b): 
            a = arr[i];
            b = arr[j];
                       
print("", a*b )

Hello, when I submit the above code to Corsera's coding judge system,

Failed case #4/17: time limit exceeded (Time used: 10.00/5.00, memory used: 22753280/2147483648.)

has been returned. How can I change it? Thank you.

Solution

  • I would first sort the values and then take the two largest elements (O(nlog(n)) vs O(n^2)):

    a, b = sorted(arr)[-2:]

    But it would be useful to know what's the domain of the values in arr (because negative numbers would break my approach).