Formatted question description: https://leetcode.ca/all/628.html
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:
- The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
- Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
Similar Questions:
Solution 1.
// OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
// 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/
// 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]);
}
};
Java
class Solution {
public int maximumProduct(int[] nums) {
int length = nums.length;
Integer[] array = new Integer[length];
for (int i = 0; i < length; i++)
array[i] = nums[i];
Arrays.sort(array, new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
if (Math.abs(num1) != Math.abs(num2))
return Math.abs(num2) - Math.abs(num1);
else
return num2 - num1;
}
});
List<Integer> zeroList = new ArrayList<Integer>();
List<Integer> positiveList = new ArrayList<Integer>();
List<Integer> negativeList = new ArrayList<Integer>();
for (int i = 0; i < length; i++) {
int num = array[i];
if (num > 0)
positiveList.add(num);
else if (num < 0)
negativeList.add(num);
else
zeroList.add(num);
}
int zeroCount = zeroList.size(), positiveCount = positiveList.size(), negativeCount = negativeList.size();
if (negativeCount == 0) {
if (positiveCount >= 3)
return positiveList.get(0) * positiveList.get(1) * positiveList.get(2);
else
return 0;
} else if (negativeCount == 1) {
if (positiveCount >= 3)
return positiveList.get(0) * positiveList.get(1) * positiveList.get(2);
else {
if (zeroCount > 0)
return 0;
else if (positiveCount >= 2)
return positiveList.get(positiveCount - 1) * positiveList.get(positiveCount - 2) * negativeList.get(negativeCount - 1);
else
return 0;
}
} else {
int max = 0;
if (positiveCount >= 3)
max = Math.max(max, positiveList.get(0) * positiveList.get(1) * positiveList.get(2));
if (positiveCount >= 1) {
max = Math.max(max, positiveList.get(0) * negativeList.get(0) * negativeList.get(1));
} else {
if (zeroCount > 0)
return 0;
else
return negativeList.get(negativeCount - 1) * negativeList.get(negativeCount - 2) * negativeList.get(negativeCount - 3);
}
return max;
}
}
}