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.
给一个整数数组，找出乘积最大的3个数，返回这3个数组。
解法：这题的难点主要是要考虑到负数和0的情况。最大乘积可能是最大的3个正数相乘或者是最小的2个负数和最大的1个正数相乘。
Java:
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n > max2) {
max3 = max2;
max2 = n;
} else if (n > max3) {
max3 = n;
}
if (n < min1) {
min2 = min1;
min1 = n;
} else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}
Python:
# Time: O(n)
# Space: O(1)
class Solution(object):
def maximumProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
min1, min2 = float("inf"), float("inf")
max1, max2, max3 = float("-inf"), float("-inf"), float("-inf") for n in nums:
if n <= min1:
min2 = min1
min1 = n
elif n <= min2:
min2 = n if n >= max1:
max3 = max2
max2 = max1
max1 = n
elif n >= max2:
max3 = max2
max2 = n
elif n >= max3:
max3 = n return max(min1 * min2 * max1, max1 * max2 * max3)
Python:
def maximumProduct(self, nums):
nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])
Python:
def maximumProduct(self, nums):
a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)
return max(a[0] * a[1] * a[2], b[0] * b[1] * a[0])
C++:
class Solution {
public:
int maximumProduct(vector<int>& nums) {
int mx1 = INT_MIN, mx2 = INT_MIN, mx3 = INT_MIN;
int mn1 = INT_MAX, mn2 = INT_MAX;
for (int num : nums) {
if (num > mx1) {
mx3 = mx2; mx2 = mx1; mx1 = num;
} else if (num > mx2) {
mx3 = mx2; mx2 = num;
} else if (num > mx3) {
mx3 = num;
}
if (num < mn1) {
mn2 = mn1; mn1 = num;
} else if (num < mn2) {
mn2 = num;
}
}
return max(mx1 * mx2 * mx3, mx1 * mn1 * mn2);
}
};
类似题目：
[LeetCode] 152. Maximum Product Subarray 求最大子数组乘积