Find maximum product of two integers in an array

Example – A = [-3,-5, 1,2,-1,5,3]

Output – 15 (-3,-5) or (3,5)

Approaches

1. Naive O(n^2) – Check for each and every pair and find the maximum product.
2. Sorting O(nlogn) – Sort the array and get the values of the maximum, second maximum, minimum and second minimum. Evaluate maximum with second max, and minimum with second min. Find the max of the two results.
3. Linear O(n) – Get the maximum, second maximum, minimum, second minimum on single traversal of the array and evaluate the max out of the two.