从数组中找出乘积最大的三个数

题目：

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1) 
输入描述:
无序整数数组A[n]

输出描述:
满足条件的最大乘积

输入例子1:
3 4 1 2

输出例子1:
24

思路：

由于空间复杂度和时间复杂度的要求，肯定无法先排序，因为排序最好时为O(n).整数的值任意需要分情况讨论

1.当数组的最大值<=0或者是数组的最小值>=0时,乘积最大就是数组中TOP3的乘积；

2.除第一种情况外，就需要考虑数组中的最大的3个数和最小的2个数，因为最大乘积肯定是在（2小+1大）或（3大）   中取得，因此比较两种记过就可得到最大乘积。

因此分析的，通过遍历数组有限次就可以实现该算法。最多需要遍历3次数组，额外空间最多为10个字节。满足算法要求

代码

public static void  pinduoduo()
	{
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		long a[]=new long[N];
		for(int i=0;i<N;i++)
			a[i]=sc.nextInt();
		System.out.println(multiple(a));
	}
	public static long multiple(long a[])
	{
		int max_index=0;//最大对应的下标
		int min_index=0;//最小值对应的下标
		for(int i=1;i<a.length;i++)
		{
			if(a[min_index]>a[i])
				min_index=i;
			else if(a[max_index]<a[i])
				max_index=i;
		}

		long result=1;
		if(a[max_index]<=0||a[min_index]>=0)
		{
			result=result*a[max_index];
			long temp1=Long.MIN_VALUE;//数组的第二大值
			int index=-1;
			for(int i=0;i<a.length;i++)
			{
				if(i!=max_index&&a[i]>temp1)
					{
					temp1=a[i];
					index=i;
					}
			}
			result=result*temp1;
			temp1=Long.MIN_VALUE;//数组的第三大值
			int index2=-1;
			for(int i=0;i<a.length;i++)
			{
				if(i!=max_index&&i!=index&&a[i]>temp1)
					{
					temp1=a[i];
					index2=i;
					}
			}
			result=result*temp1;
			return result;
		}
		else if(a[max_index]>0&&a[min_index]<0)
		{
			long tempmin_2=Long.MAX_VALUE,index_min2=-1;//数组的第二小值对应的值和下标
			long tempmax_2=Long.MIN_VALUE,index_max2=-1;//数组的第二大值对应的值和下标
			long tempmax_3=Long.MIN_VALUE,index_max3=-1;//数组的第三大值对应的值和下标
			for(int i=0;i<a.length;i++)
			{
				if(i!=min_index&&a[i]<tempmin_2)
					{
					tempmin_2=a[i];
					index_min2=i;
					}
				if(i!=max_index&&a[i]>tempmax_2)
				{
					tempmax_2=a[i];
					index_max2=i;
				}
			}
			for(int i=0;i<a.length;i++)
			{
				if(i!=max_index&&i!=index_max2&&a[i]>tempmax_3)
				{
					tempmax_3=a[i];
					index_max3=i;
				}
			}
			long result1=a[min_index]*tempmin_2*a[max_index];
			long result2=a[max_index]*tempmax_2*tempmax_3;
			return result1>result2?result1:result2;
		}
		return 0;
	}