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.
1using System;
2
3public class MaxProduct {
4 public static int MaximumProduct(int[] nums) {
5 Array.Sort(nums);
6 int n = nums.Length;
7 return Math.Max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
8 }
9
10 public static void Main() {
11 int[] nums = {1, 2, 3, 4};
12 Console.WriteLine(MaximumProduct(nums));
13 }
14}After sorting the array, the code calculates and compares the potential maximum products, returning the greater one.
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).
1using System;
public class MaxProductSinglePass {
public static int MaximumProduct(int[] nums) {
int max1 = int.MinValue, max2 = int.MinValue, max3 = int.MinValue;
int min1 = int.MaxValue, min2 = int.MaxValue;
foreach (int num in 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 Math.Max(max1 * max2 * max3, min1 * min2 * max1);
}
public static void Main() {
int[] nums = {1, 2, 3, 4};
Console.WriteLine(MaximumProduct(nums));
}
}The algorithm retains the top three highest and two lowest numbers during a single pass to efficiently determine the potential maximum products.