寻找乘积最大的三个数
程序员文章站
2024-03-16 18:03:10
...
寻找乘积最大的三个数
题设要求:给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)
输入描述:无序整数数组A[n]
输出描述:满足条件的最大乘积
输入例子1:3 4 1 2
输出例子1:24
问题分析:在数组中存在负数、正数、0的情况下,要获得三个数乘积最大,必然是最大的三个正数或者两个最小的负数和一个最大的正数。也就是说,其实这道题只要找到最大的三个数和最小的两个数即可(不包括0)。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] array = new long[n];
for(int i=0;i<n;i++){
array[i] = sc.nextLong();
}
System.out.print(MaxProduct(array,n));
}
static long MaxProduct(long[] nums, int len){
long max1=0,max2=0,max3=0,min1=0,min2=0;
for(int i=0;i<len;i++)
{
if(nums[i]!=0){
if(nums[i]>max1){
max3=max2;
max2=max1;
max1=nums[i];
}else if(nums[i]>max2){
max3=max2;
max2=nums[i];
}else if(nums[i]>max3){
max3=nums[i];
}else if(min1<=nums[i]&&nums[i]<min2){
min2=nums[i];
}else if(nums[i]<min1){
min2=min1;
min1=nums[i];
}else{
continue;
}
}
}
long result = Math.max(max1*max2*max3,min1*min2*max1);
return result;
}
}