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#
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.