[数据结构与算法]求数组中三个数乘积的最大值（Java）

求数组中三个数乘积的最大值

（牛客网—牛客题霸算法篇—NC106）

题目描述

给定一个长度为 n的无序数组 A ，其中包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度：O(n) ，空间复杂度： O(1）。

思路

Java实现
由于数组中存在负数，负负得正，因此可能两个负数相乘的成绩大于两个负数相乘，因此定义5个变量，存放最大的三个数和最小的两个数，依次遍历数组。
最后得到最大的三个数和最小的两个数，用最大的三个数的乘积与最小的两个数与最大值的乘积相比较，返回比较结果中较大的一个。

代码实现

import java.util.*;
public class Solution {
    public long solve (int[] A) {
        // write code here
        int minmin=Integer.MAX_VALUE;//最小的
        int min=Integer.MAX_VALUE;//倒数第二小的
        int max1 = Integer.MIN_VALUE;//最大的
        int max2 = Integer.MIN_VALUE;//倒数第二大
        int max3 = Integer.MIN_VALUE;//倒数第三大
        for(int x:A){
            if(x<minmin){
                min=minmin;
                minmin=x;
            }else if(x<min){
                min=x;
            }
            if(x>max1){
                max3=max2;
                max2=max1;
                max1=x;
            }else if(x>max2){
                max3=max2;
                max2=x;
            }else if(x>max3){
                max3=x;
            }
        }
        return Math.max((long)minmin * min * max1, (long)max1 * max2 * max3);
    }
}