You have 15 boxes, each containing a real number, ordered least-greatest. How do you find the 5 that will yield the greatest product, the quickest?

Question

As the title says, you have 15 boxes, a real number is in each, and they're ordered such that box 1 contains the lowest value, box 2 the second lowest, box 3 third lowest and so on, until box 15, which contains the highest value.

You want to be sure to pick the 5 boxes with the greatest total product, such that $$\text{box} * \text{box} * \text{box} * \text{box} * \text{box} = \text{maximum amount}$$ and you want to do this with as few operations and comparison as possible. An operation is anything like $x * x$ or $x - y$, and a comparison is anything like $a > b$. What do you do?

---

You want to be able to know that, no matter what set of 15 in-order (least-greatest) boxes you are given, you can follow this simple formula (whatever you come up with) to always come out with the greatest product of 5 of them. And you want to come out with the minimum total of operations + comparisons that will let you always do that.

And numbers are not necessarily distinct! And all 4 of the basic operators ($+, -, *, /$) are allowed, though I am pretty sure you will only need $*$ ;)

Answer 1

If we can, we must pick an even number of negative numbers. First, get the special case, where we cannot, out of the way:

if $\boxed{15} < 0$, pick $\boxed{11}\times\boxed{12}\times\boxed{13}\times\boxed{14}\times\boxed{15}$

Then we need the largest absolute value available, with the restriction that there must be an even number of negative values. So the answer is one of these:

$\boxed{11}\times\boxed{12}\times\boxed{13}\times\boxed{14}\times\boxed{15}$

$\boxed{1}\times\boxed{2}\times\boxed{13}\times\boxed{14}\times\boxed{15}$

$\boxed{1}\times\boxed{2}\times\boxed{3}\times\boxed{4}\times\boxed{15}$

Then, note that the boxes are ordered, so out of all the possible pairs of two consecutive boxes, at most one contains both a positive and a negative value. Therefore, when comparing products of two such pairs, at least one of the products is guaranteed to be non-negative, so it's safe to multiply the larger one into our solution without further checks.

So, calculate $\boxed{1}\times\boxed{2}$ and $\boxed{13}\times\boxed{14}$ and compare them. Disqualify the solution that doesn't contain the pair with the larger result.

Then, we need to compare the two remaining possibilities. Luckily, they both contain $\boxed{15}$ and the "winner" of the previous phase, and one of the possibilities contains the losing pair from the previous phase (we already know the multiplication result), so we will need to do only one more multiplication and comparison to distinguish between the two remaining cases.

So the total number of operations required for choosing the boxes is

3 multiplications and 3 comparisons.

If we want to know what the actual maximum product is, we can get that by using

two more multiplications, because we already have two of the pairwise products calculated, so we can multiply those by each other, and then multiply the result by $\boxed{15}$ to get the maximum product.

(For completeness's sake, when we detected the "all numbers negative" case, we hadn't done any multiplication yet, so in that case we can get the maximum product by using 4 multiplications.)

Answer 2

To find out which boxes to pick I need

6 operations

Use the following strategy:

Let's call $a = x_{1} \times x_{2}, b = x_{3} \times x_{4}, c = x_{11} \times x_{12}, d = x_{13} \times x_{14}, e = x_{15}$.
The best solutions can only be case 1: $c \times d \times e$ or case 2: $a \times d \times e$ or case 3: $a \times b \times e$.

If $x_{15} < 0$ then case 1 (1 comparison needed).

Now if $a < d$ we need to check $a < c$. If true, then case 1, else case 2 (3 multiplications and 2 additional comparisons needed).
Now if $a >= d$ we need to check $b < d$. If true, then case 2, else case 3 (3 multiplications and 2 additional comparisons needed).

Answer 3

Here is what I could come up with taking into account a few samples.
Let the boxes be $x_1, x_2, ... x_{15}$ then follow the following procedure:
Step 1: if $x_{15}$ is negative then take the boxes $x_{11}, x_{12}, x_{13}, x_{14}$ and $x_{15}$ else continue to next step.
Step 2: if $x_{13}$ is negative then take the boxes $x_1, x_2, x_3, x_4$ and $x_{15}$ else continue to next step.
Step 3: if $x_{11}$ is negative then go to step 4-a else go to step 4-b.
Step 4-a: take $x_1, x_2, x_3, x_4, x_{15}$ if $(x_3*x_4) > (x_{13}*x_{14})$ else take $x_{1}, x_{2}, x_{13}, x_{14}, x_{15}$. Stop.
Step 4-b: take $x_1, x_2$ and go to step 5 if $(x_1*x_2) > (x_{11}*x_{12})$ else take $x_{11}, x_{12}, x_{13}, x_{14}, x_{15}$. Stop.
Step 5: take $x_3, x_4, x_{15}$ if $(x_3*x_4) > (x_{13}*x_{14})$ else take $x_{11}, x_{12}, x_{13}, x_{14}, x_{15}$. Stop.

Case for all negatives is trivial.
Let's see some other examples:
Example 1: All positives
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Step 1 and 2 will not satisfy. In step three, 11 is positive so we go to step 4-b. Now, $(x_1*x_2) < (x_{11}*x_{12})$ so we will take 11, 12, 13, 14, 15 for max product

Example 2: 1 positive all Negatives -14 -13 -12 -11 ... -1 1
Step 1 will not satisfy but Step 2 will as $x_{13}=-2<0$ so we take -14, -13, -12, -11, 1 which will give max product

Example 3: 4 non-negatives and other negatives
-11 -10 ... -1 0 1 2 3
Step 1 and 2 will not satisfy. In step 3, -1 is negative so we go to step 4-1. In step 4-a, we see $(x_3*x_4) > (x_{13}*x_{14})$ so we will take -11, -10, -9, -8, 3 to get the max product.

In my opinion this involves quite less number of computations, if not the least. Including every multiplication and every comparison as one operation, this takes 9 steps in worst case scenario

I have written a code in C++ to test this which can be found at https://ideone.com/pppGuD