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; } } } -
// 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]); } }; -
class Solution(object): def maximumProduct(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort() return max(nums[0] * nums[1] * nums[-1], nums[-1] * nums[-2] * nums[-3])