A non-empty zero-indexed array T consisting of N integers is given.
The product of triplet (A, B, C) equates T[A] x T[B] x T[C] (0 ≤ A < B < C < N)
For example, array T such that:
T[0] = -6
T[1] = 2
T[2] = 4
T[3] = -5
T[4] = 10
T[5] = 12
The maximal product of the triplet is (2,4,5) value is 4 * 10 * 12 = 480
Your goal is to write a function to find the maximal product of any triplet.
From the example above the function should return 480
Assumption
N is an integer within the range [3…100,000]
each element of array T is an integer within the range [−1,000…1,000]
Complexity
expected worst-case time complexity is O(N*log(N));