题目描述
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述:
无序整数数组A[n]
输出描述:
满足条件的最大乘积
示例1
输入
复制
3 4 1 2
输出
复制
24
思路
/定义五个数，一个最大，一个次大，一个第三大，一个最小，一个次小。
只要找到这五个数，问题就解决了。因为最大乘积只可能是
最大（次大第三大） 或者是 最大（最小次小）。时间复杂度O(n),
空间复杂度O(1)。PS：这道题输入有问题，题目给的样例是直接给了一组数，
而此时用例先给了一个数的个数n，然后再给了一组数/
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(); } getTheMostValue(array,n); } public static void getTheMostValue(long[] num,int len){ long max1=0;long max2=0;long max3=0;long min1=0;long min2=0; for(int i=0;i<len;i++){ if(num[i]>max1){ max3=max2; max2=max1; max1=num[i]; }else if(num[i]>max2){ max3=max2; max2=num[i]; }else if(num[i]>max3){ max3=num[i]; }else if(num[i]<min1){ min2=min1; min1=num[i]; }else if(num[i]>min1&&num[i]<min2){ min2=num[i]; } } long max=Math.max(max1*max2*max3,max1*min1*min2); System.out.println(max); } }
