Max product of three

We have a vector of something in between three and 100,000 integers in the range [−1,000 ... 1,000]. We want to get the maximum product of three elements among all the possible choices.

I found this problem in the Codility train page, section Sorting, under the nickname Max-product-of-three.

It looks very simple, and actually it is. Just be careful in considering the properties of multiplication.

A few test cases (written in C++ for the GoogleTest framework) would help to implement correctly the solution:

int solution(std::vector<int>& input);

TEST(MPoT, Given) // 1
{
    std::vector<int> input;
    input.push_back(-3);
    input.push_back(1);
    input.push_back(2);
    input.push_back(-2);
    input.push_back(5);
    input.push_back(6);

    ASSERT_EQ(60, solution(input));
}

TEST(MPoT, AllNeg) // 2
{
    std::vector<int> input;
    input.push_back(-2);
    input.push_back(-3);
    input.push_back(-4);
    input.push_back(-1);

    ASSERT_EQ(-6, solution(input));
}

TEST(MPoT, SomeNeg) // 3
{
    std::vector<int> input;
    input.push_back(0);
    input.push_back(-3);
    input.push_back(-4);
    input.push_back(1);
    input.push_back(2);

    ASSERT_EQ(24, solution(input));
}

1. This test case is part of the Codility's problem description.
2. What if all the input elements are negative.
3. More interestingly, when a mix of positive and negative numbers are in the game, the weight of the biggest negative ones should be considered.

The first idea that I guess anyone would have is getting the three biggest elements and multiplying them. That works fine in the first two test cases, but fails spectacularly in the third one. We (or at least, I) have forget to consider the case when we have some big negative values.

Remembering that also negative values could contribute to the solution, as showed in the third test case, I came up with this piece of code:

int solution(std::vector<int>& input)
{
    std::sort(input.begin(), input.end(), std::greater<int>()); // 1
    int alpha = input[0] * input[1] * input[2]; // 2
    int beta = *input.rbegin() * *(input.rbegin()+1) * input[0]; // 3

    return alpha > beta ? alpha : beta; // 4
}

1. Actually, there is not any real advantage in sorting the array in descending order. Notice that, as required by the Codility conditions, I am modifying the input vector. This is usually not considered a bright idea.
2. Having sorted the vector from the biggest element downward, I multiply the three elements more to the left. Often this would give the result we are looking for.
3. We could have the case where taking the two most negative numbers in the sequence have a higher relevance of the second and third positive numbers. In this case beta would be bigger than alpha.
4. Now it is just a matter of comparing alpha and beta, and returning the biggest one.