An antique auction house is assembling a flagship showcase bundle for its next event. Every lot in the current catalog has been assigned an integer valuation, which may be positive (a prized piece) or negative (a lot burdened with restoration costs that drag its displayed worth below zero). The house wants to select exactly three lots to bundle together, and defines the showcase impact of a bundle as the product of the three chosen valuations — a bundle built from two heavily negative lots and one strongly positive lot can produce an unexpectedly large positive impact once the two negatives cancel out. Given the valuations of every lot in the catalog, find the maximum showcase impact achievable by any bundle of exactly three lots.
The first line contains a single integer n, the number of lots in the catalog. The second line contains n space-separated integers a_1, a_2, ..., a_n — the valuation of the i-th lot.
Print a single integer: the maximum product obtainable by choosing exactly three of the n valuations.
Example 1
Input
5 3 1 5 -2 -4
Expected
40
Explanation
Sorting the valuations gives -4, -2, 1, 3, 5. The three largest positive lots (1, 3, 5) bundle to 15, but pairing the two negative lots -4 and -2 with the single largest lot 5 gives (-4) * (-2) * 5 = 40, since the two negatives cancel out. 40 is the maximum achievable showcase impact.
Example 2
Input
4 -1 -2 -3 -4
Expected
-6
Explanation
Every lot has a negative valuation, so any bundle of three produces a negative product. To maximize (make the product least negative), choose the three valuations closest to zero: -1, -2, -3, giving (-1) * (-2) * (-3) = -6, which is larger than any other combination of three lots from this catalog.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →