MaxProductOfThree
You are given an array A of N integers. You must find the maximum product of any triplet A[P], A[Q], A[R].
Language used: C#
Assumptions:
N must range from 3 to 100,000. Each element of A will range from -1000 to 1000. O(N*log(N)) time complexity is required.
Solution
Yes, sorting the array and taking the last three elements (largest positive elements) will give you a candidate for the maximum product of three, however take in mind that each int may be as low as -1000. Therefore multiplying the two most negative values by the largest positive value is also a candidate. The largest most positive candidate is the answer.