Lesson06(Sorting)-MaxProductOfThree.cpp

// 2. MaxProductOfThree.

/**
 * A non-empty array A consisting of N integers is given.
 * The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).
 * 
 * For example, array A such that:
 *       A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6
 * 
 * contains the following example triplets:
 *       • (0, 1, 2), product is −3 * 1 * 2 = −6
 *       • (1, 2, 4), product is 1 * 2 * 5 = 10
 *       • (2, 4, 5), product is 2 * 5 * 6 = 60
 * 
 * Your goal is to find the maximal product of any triplet.
 * 
 * Write a function:
 *       class Solution { public int solution(int[] A); }
 * that, given a non-empty array A,
 * returns the value of the maximal product of any triplet.
 * 
 * Write an efficient algorithm for the following assumptions:
 *       • N is an integer within the range [3..100,000];
 *       • each element of array A is an integer within the range [−1,000..1,000].
 */

#include <vector>
#include <algorithm>

int maxProductOfThree(std::vector<int>& A)
{
    int n = (int)A.size();
    if (n < 3) {
        return 0;
    }

    // Sort the input vector in ascending order.
    std::sort(std::begin(A), std::end(A));

    // The maximum product of the 3 elements in a sorted vector can take on one of 4 values:
    // 1. Multiplying the first 3 elements.
    // 2. Multiplying the last 3 elements (which may signify the highest positive values).
    // 3. Multiplying the first element with the last 2 elements.
    // 4. Multiplying the first 2 elements with the last element
    //    (accounting for the potential scenario of 2 first large negative values becoming positive when multiplied
    //     and also multiplied with the last positive value).
    int tripletProduct1 = A[0] * A[1] * A[2],
        tripletProduct2 = A[n - 1] * A[n - 2] * A[n - 3],
        tripletProduct3 = A[0] * A[n - 1] * A[n - 2],
        tripletProduct4 = A[0] * A[1] * A[n - 1];

    return std::max(std::max(tripletProduct1, tripletProduct2),
        std::max(tripletProduct3, tripletProduct4));
}