628. Maximum Product of Three Numbers
1. Description
Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
2. Example
Example 1:
Input: nums = [1,2,3]
Output: 6
Example 2:
Input: nums = [1,2,3,4]
Output: 24
Example 3:
Input: nums = [-1,-2,-3]
Output: -6
3. Constraints
- 3 <= nums.length <= $10^4$
- -1000 <= nums[i] <= 1000
4. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
// the range of numbers is [-1000, 1000]
// so the min two negative numbers' product maybe very big
// so, we need to check max three numbers' product and min two numbers and one max number's product
class Solution
{
public:
// int maximumProduct(vector<int>& nums)
int maximumProduct(vector<int> &i_nums)
{
vector<int> maxThreeValues, minTwoValues;
for(int i = 0; i < i_nums.size(); i++)
{
minTwoValues.push_back(i_nums[i]);
maxThreeValues.push_back(i_nums[i]);
sort(minTwoValues.begin(), minTwoValues.end());
sort(maxThreeValues.begin(), maxThreeValues.end(), [](int left, int right){return left > right;});
if(minTwoValues.size() > 2) minTwoValues.pop_back();
if(maxThreeValues.size() > 3) maxThreeValues.pop_back();
}
return max(maxThreeValues[0] * minTwoValues[0] * minTwoValues[1], maxThreeValues[0] * maxThreeValues[1] * maxThreeValues[2]);
}
};