Highest Product of X Items How do you find the highest product of X items?
This should optimize for runtime complexity and protect from overflows from large products.

Inputs

An array of both positive and negative Ints representing potential products to the solution
An Int representing the number of products required for the solution


Output: An Int representing the highest product of X amount of numbers.

For example, for the highest product of 3 items, the input is iterated through while updating the following variables. After the iteration has completed in $O(n)$ time, the highest product of three variable is returned as the solution.

Lowest number
Highest number
Lowest product of two
Highest product of two
Highest product of three
Let the integers be $a_1,a_2,\dots,a_n$ sorted in decreasing order of magnitude, so $|a_1| \ge |a_2| \ge \cdots$, and suppose you want to find the product of $k$ of them that is as large as possible.
Then:

If $a_1 \times \cdots \times a_k$ is positive, it is the solution.

Otherwise, if $a_{k+1}$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit $a_i$ from the product, where $a_i$ is the largest of the negative numbers in $a_1,\dots,a_k$, i.e., closest to zero).

Otherwise, if $a_{k+1}$ is negative and at least one of $a_1,\dots,a_k$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit the smallest positive number of $a_1,\dots,a_k$ from the product).

Otherwise, if at least one of $a_1,\dots,a_n$ is positive, the solution is $a_1 \times \cdots \times a_{k-1} \times a_j$ where $a_j$ is the largest positive number in $a_1,\dots,a_n$.

If all of $a_1,\dots,a_n$ are negative and $k$ is odd, then the solution is $a_{n-k+1} \times \dots \times a_n$.


This can be computed in $O(n \lg k)$ time using a heap of size $k$.