Maximum Product of Three Numbers

Problem

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

Constraints

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

Solution

The problem Maximum Product of Three Numbers can be solved by sorting the given array. When the array is sorted, we can think of 3 cases: when there are only positive numbers, when there are only negative numbers and when both positive and negative number exists. In the first case, maximum product can be gained using the last three elements as it would yield a positive result with the biggest absolute value. In the second case, maximum product can once again be gained using the last three elements as it would yield a negative result with the smallest absolute value. Finally, in the third case, we only need to compare the product of first 2 elements and the product of second to last and third to last elements as the last element always need to be included. All things considered, the problem can be simplified into comparing products of 2 pairs of 3 elements.

Implementation

class Solution
{
  public:
    int maximumProduct(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());

        int len = nums.size();
        return max(nums[0] * nums[1] * nums[len - 1], nums[len - 3] * nums[len - 2] * nums[len - 1]);
    }
};