Leetcode - 628 Maximum Product of Three Numbers
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:
题解：
O(n) 的时间复杂度， 将整个数组扫一遍， 找到最大的三个数， 和最小的两个数（有可能是负数）， 在他们的组合中中找最大。
class Solution {
public:
int maximumProduct(vector<int>& nums) {
int ans, fs_m=1000 , sd_m=1000, th_m=1000, fs=-1000, sd=-1000, th=-1000;
for(int i=0; i<nums.size(); ++i){
if(nums[i] >= fs){
th = sd;
sd = fs;
fs = nums[i];
}else if(nums[i] >= sd){
th = sd;
sd = nums[i];
}else if(nums[i] > th){
th = nums[i];
}
if(nums[i] < fs_m){
th_m = sd_m;
sd_m = fs_m;
fs_m = nums[i];
}else if(nums[i] <= sd_m){
th_m = sd_m;
sd_m = nums[i];
}else if(nums[i] < th_m){
th_m = nums[i];
}
}
ans = max(-1000000000, th*sd*fs);
ans = max(ans, fs*sd_m*fs_m);
return ans;
}
};
Leetcode - 628 Maximum Product of Three Numbers
原文：http://www.cnblogs.com/zhang-yd/p/7082714.html