Sponsored
Sponsored
This approach involves sorting the array, and then choosing the maximum product by examining either the product of the three largest numbers or the product of the two smallest numbers and the largest number.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we use in-place sorting.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maximumProduct(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int n = nums.size();
8 return std::max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
9}
10
11int main() {
12 std::vector<int> nums = {1, 2, 3, 4};
13 std::cout << maximumProduct(nums) << std::endl;
14 return 0;
15}The solution begins by sorting the vector. After sorting, the two potential products that could be maximal are compared. These are the product of the three largest numbers and the product of the two smallest numbers with the largest number.
This approach involves finding the largest three and smallest two numbers in a single traversal of the array. This avoids sorting and gives a more optimal solution for time complexity.
Time Complexity: O(n) as there's only a single pass through the array.
Space Complexity: O(1).
1
We maintain variables for the three largest and two smallest numbers as we iterate. This allows us to compute the potential maximum products and choose the maximum one without needing to sort the array.