Given a list of numbers, how would you determine the maximum pairwise product of numbers in the list?
For example, if we have the list [1; 3; 5; -2] the maximum pairwise product is 15, which is the product of 3 and 5.
The straigt-forward approach is to compute all possible pairwise products and identify the maximum among the intermediate results:
Since we have two loops that iterate over the list of numbers, the time complexity is O(n2).
Can we do better? Yes, we can. The idea is to find the maximum and the second maximum elements in the list - and their product would be the maximum pairwise product.