Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1: Input: [1,2,3] Output: 6

Example 2: Input: [1,2,3,4] Output: 24

Solution: Sorting

1. Sort the array using some efficient in-place sorting algorithm in ascending order.
2. Return the maximum of product of last three elements of the array and product of first two elements and last element.

Solution: Find maximum, second maximum and third maximum

1. Scan the array and compute Maximum, second maximum and third maximum element present in the array.
2. Scan the array and compute Minimum and second minimum element present in the array.
3. Return the maximum of product of Maximum, second maximum and third maximum and product of Minimum, second minimum and Maximum element.

Note: the key is to figure out how to find the second maximum and third maximum.

int maximumProduct(vector<int>& nums) {
    int maxA = INT_MIN;
    int maxB = INT_MIN;
    int maxC = INT_MIN;

    int minA = INT_MAX;
    int minB = INT_MAX;

    for(auto num: nums) {
        if(num > maxA) {
            maxC = maxB;
            maxB = maxA;
            maxA = num;
        } else if(num > maxB) {
            maxC = maxB;
            maxB = num;
        } else if(num > maxC) {
            maxC = num;
        }

        if(num < minA) {
            minB = minA;
            minA = num;
        } else if(num < minB) {
            minB = num;
        }
    }

    return max(maxA * maxB * maxC, minA * minB * maxA);
}