432. Maximum Product of Three Numbers
You are given an integer array nums with at least three elements. Pick three entries (three distinct positions — equal values are fine) so that their product is as large as possible.
Return that maximum product.
Watch the signs: the array may contain negative numbers, and two negatives multiply into a positive.
Example 1:
Input: nums = [4, 5, 1, 3]
Output: 60
Explanation: The three largest values are 4, 5, and 3, and 4 · 5 · 3 = 60 beats every other triple.
Example 2:
Input: nums = [-8, -7, 2, 3]
Output: 168
Explanation: The two most-negative values pair into a large positive: (−8) · (−7) · 3 = 168, far better than 2 · 3 times anything.
Constraints:
- 3 ≤ nums.length ≤ 10⁴
- -1000 ≤ nums[i] ≤ 1000
Hints:
If every number were positive, the answer would just be the product of the three largest. What changes when negatives appear?
Two negatives make a positive — so a huge product can also come from the two smallest (most negative) values times the single largest value.
Only two candidates can win: (largest three) or (smallest two × largest one). You can find those five numbers in one pass without sorting.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 5, 1, 3]
Expected output: 60