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 个都是正数最大, 2 个是负数最小, 一个是正数最大比大小.
- class Solution {
- public:
- int maximumProduct(vector<int>& nums) {
- if(nums.size()<3) return 0;
- if(nums.size()==3) return nums[0]*nums[1]*nums[2];
- int max_product=1;
- int max_neg=1;
- int n =nums.size();
- sort(nums.begin(),nums.end());
- if(nums[n-3]>=0)
- max_product = nums[n-3]*nums[n-2]*nums[n-1];
- if(nums[1]<=0)
- max_neg=nums[0]*nums[1]*nums[n-1];
- return max_product>=max_neg?max_product:max_neg;
- }
- };
来源: http://www.bubuko.com/infodetail-2563160.html