从 3 中求中间元素(求三元组的最大乘积)

Question

这是我第一次问SO，所以如果我的帖子有错误或问题，请告诉我，我会编辑以使其更好。

我需要在数组中找到三元组的最大乘积，在最好的复杂性下，我认为我做得很好，但我卡在最后一部分，因为我找不到 3 之间的元素(正数中间和负数中间(，找到最大值和最小值我想不是什么大问题，但如果也有错误，我很乐意做任何笔记。 我的代码： (我们可以假设数组至少有 3 个元素(

public static int findTriplet (int[] arr){
int max1 = Integer.MIN_VALUE , max2 = Integer.MIN_VALUE , max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE , min2 = Integer.MAX_VALUE , min3 = Integer.MAX_VALUE;
int countPos = 0 , countNeg = 0;
for (int i = 0; i < arr.length; i++){
if (arr[i]> 0){
countPos++; //counter for positive values
if(arr[i]>max1){ //updating maximum value 1
max2 = max3;
max3 = max1;
max1=arr[i];
}
else if(arr[i]>max3){ //updating maximum value 2
max2 = max3;
max3 = arr[i];
}
else if(arr[i]>max2){ //updating maximum value 3
max2 = arr[i];
}
else{ //else if the value is negative
countNeg++;
if (arr[i]<min1){ //updating minimum value 1
min2 = min3;
min3 = min1;
min1 = arr[i];
}
else if (arr[i]<min2){ //updating minimum value 2
min3 = min2;
min2 = arr[i];
}
else if (arr[i]<min3){ //updating minimum value 3
min3 = arr[i];
}
}
}
}
int maxPositive = Math.max(max1, Math.max(max2, max3));
int minPositive = Math.min(max1, Math.min(max2, max3));
int maxNegative = Math.max(min1, Math.max(min2, min3));
int minNegative = Math.min(min1, Math.min(min2, min3));
if(countPos==3){
return max1*max2*max3;
}
else if(countPos == 2){
}
}

感谢您的任何帮助，将不胜感激以最小的时间复杂度找到中间值的任何帮助和提示，当然也非常感谢任何改进说明。

Answer 1

你不需要最少三个。 两个最小值和一个最大值的乘积将是最大值(假设最小值为负数。否则，答案将是三个最大值的乘积。

一个解决方案：

public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
for(int i : nums) {
if(i >= max1) {
max3 = max2;
max2 = max1;
max1 = i;
}
else if( i <= max1 && i >= max2) {
max3 = max2;
max2 = i;
}
else if( i <= max1 && i <= max2 && i >= max3) {
max3 = i;
}
if(i <= min1) {
min2 = min1;
min1 = i;
}
else if(i <= min2 && i >= min1) {
min2 = i;
} 
}
return Math.max(max1*max2*max3, min1*min2*max1);    
}