Short Problem Definition:
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(1)
After sorting the largest product can be found as a combination of the last three elements. Additionally, two negative numbers add to a positive, so by multiplying the two largest negatives with the largest positive, we get another candidate. If all numbers are negative, the three largest (closest to 0) still get the largest element!
def solution(A): if len(A) < 3: raise Exception("Invalid input") A.sort() return max(A * A * A[-1], A[-1] * A[-2] * A[-3])
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.