628

628. Maximum Product of Three Numbers (Easy)

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

 

Note:

1. The length of the given array will be in range [3,10⁴] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

 

Related Topics:
Array, Math

Similar Questions:

• Maximum Product Subarray (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maximumProduct(vector<int>& A) {
        sort(begin(A), end(A));
        return A.back() * max(A[A.size() - 2] * A[A.size() - 3], A[0] * A[1]);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maximumProduct(vector<int>& A) {
        vector<int> maxVals(3, INT_MIN), minVals(2, INT_MAX);
        for (int n : A) {
            for (int i = 0; i < 3; ++i) {
                if (n <= maxVals[i]) continue;
                for (int j = 2; j > i; --j) maxVals[j] = maxVals[j - 1];
                maxVals[i] = n;
                break;
            }
            for (int i = 0; i < 2; ++i) {
                if (n >= minVals[i]) continue;
                for (int j = 1; j > i; --j) minVals[j] = minVals[j - 1];
                minVals[i] = n;
                break;
            }
        }
        return maxVals[0] * max(maxVals[1] * maxVals[2], minVals[0] * minVals[1]);
    }
};