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

题目描述
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述:
输入共2行，第一行包括一个整数n，表示数组长度
第二行为n个以空格隔开的整数，分别为A1,A2, … ,An
输出描述:
满足条件的最大乘积
示例1
输入
4
3 4 1 2
输出
24

package lianxi;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main{


    //暴力求解数组中三个数的最大乘机
    public static int maxMuti1(int [] arr){

        int max=-Integer.MAX_VALUE;
        for (int i = 0; i <arr.length ; i++) {
            for (int j = i+1; j <arr.length ; j++) {
                for (int k = j+1; k <arr.length ; k++) {
                    if(arr[i]*arr[j]*arr[k]>max){
                        max=arr[i]*arr[j]*arr[k];
                    }
                }
            }
        }
        return max;
    }


    //求全是正数的数组中最大三个数的乘机
    //两个最小负数和一个最大的正数
    public static long maxMuti2(int[] arr){

        ArrayList<Integer> list = new ArrayList<>(arr.length);
        for (int i = 0; i <arr.length ; i++) {
            list.add(arr[i]);
        }
        Collections.sort(list);//排序（从小到大）
        Collections.reverse(list);//反转（从大到小）

        //现在数组内是从大到小排列的

           if(list.get(0)<0){//如果最大的数小于0，那么三个负数乘机一定小于0，这时就找三个最小的负数相乘，才能最大
            return (long)list.get(0)*list.get(1)*list.get(2);
         } else {//最大的数大于0
            //就比较最大的三个数的乘积和最小的两个数与最大的数的乘机,谁大返回谁
            return Math.max((long)list.get(0)*list.get(1)*list.get(2),(long)list.get(0)*list.get(list.size()-1)*list.get(list.size()-2));
            }
    }
    
       public static void main(String []args){

           Scanner scanner = new Scanner(System.in);
           int n=scanner.nextInt();//输入数组大小
           int arr[]=new int[n];
           for (int i = 0; i <n ; i++) {
               arr[i]=scanner.nextInt();//给数组输入值
           }
           long max = maxMuti2(arr);
           System.out.println(max);
       }

}