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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int *)a - *(int *)b);
6}
7
8int maximumProduct(int* nums, int numsSize){
9 qsort(nums, numsSize, sizeof(int), compare);
10 int a = nums[numsSize - 1] * nums[numsSize - 2] * nums[numsSize - 3];
11 int b = nums[0] * nums[1] * nums[numsSize - 1];
12 return a > b ? a : b;
13}
14
15int main() {
16 int arr[] = {1, 2, 3, 4};
17 int size = sizeof(arr) / sizeof(arr[0]);
18 printf("%d\n", maximumProduct(arr, size));
19 return 0;
20}We sort the array using the standard library function qsort. After sorting, the maximum product can either be from the three largest numbers or from the product of the two smallest numbers and the largest number. This is due to the potential for large negative numbers producing a positive product.
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#include <iostream>
2#include <vector>
#include <limits.h>
int maximumProduct(std::vector<int>& nums) {
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (int num : nums) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
return std::max(max1*max2*max3, min1*min2*max1);
}
int main() {
std::vector<int> nums = {1, 2, 3, 4};
std::cout << maximumProduct(nums) << std::endl;
return 0;
}By iterating once through the vector while maintaining the top three largest and two smallest values, we can determine the maximum product efficiently.