Pairwise Max Product

Question

This python program takes user input of the number of elements in a list in the variable b and then takes user input of the list elements in list a. It then finds out the maximum product of a pair of the list elements.

For example, if the list elements are 5,4 and 6, then the maximum product is 30.

Can we simplify it in a way such that it takes less time than this?

The error I am getting is:

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

b=int(input())
a=list(map(int,input().split()))
maxprod=0
for i in range(b):
    for j in range(i+1,b):
        maxprod=max(maxprod,a[i]*a[j])
print(maxprod)

Answer 1

Making it faster

The maximum product of two numbers in the input will be either:

• the product of the two highest numbers
• the product of the two lowest numbers
  • note that this is possible when the lowest numbers are negative

So you can find the two highest and two lowest values, and decide which product is higher and return it.

This can be done in \$O(n)\$ time, which will be much faster than the current \$O(n^2)\$ solution for large inputs.

def pairwise_max_product(nums):
    """
    >>> pairwise_max_product([3, 2])
    6

    >>> pairwise_max_product([3, 2, -5, -6])
    30

    >>> pairwise_max_product([-2, 1, 1])
    1

    >>> pairwise_max_product([-2, -2, 1, 1])
    4
    """

    assert len(nums) >= 2

    def top2(key=lambda x: x):
        second, first = sorted(nums[0:2], key=key)
        for current in nums[2:]:
            if key(first) < key(current):
                second = first
                first = current
            elif key(second) < key(current):
                second = current

        return first, second

    max1, max2 = top2()
    min1, min2 = top2(lambda x: -x)

    return max(max1 * max2, min1 * min2)

Beware of corner cases

If there are less than two numbers, the program outputs 0. For a list with a single element, say [3], printing that the maximum product of two pairs of numbers is 0 would seem strange.

Use descriptive variable names

It's hard to remember what is what, when variables don't have descriptive names, such as a and b. nums and nums_count would help a lot.

Use functions

The code reads input from stdin, computes something, then prints to stdout. The computation part can be turned into a function that takes a list of numbers and returns the maximum product. It will have a single responsibility, to compute the maximum product, and a reader can focus on making it fulfill that one responsibility:

def pairwise_max_product(nums):
    ...

Note that nums_count = len(nums).

Follow the style guide

Python has an official style guide PEP-8, it's good to follow it. For example, it's recommended to put spaces around operators, for example instead of range(i+1,b), write range(i + 1, b).