NC106 三个数的最大乘积 算法java实现

题目描述

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。
示例1
输入：[3,4,1,2]
返回值：24

解题思路

该题的测试用例：[2,5,3,1] ， [-8,-2,-5,-1]， [-5,-1,6,3]，[-3,-1,5,0,2]，[-1,5,0,2]，还有要注意当乘积超过int的时候应该用long来存结果，通过分析可得知，这些组合中智存在两种计算方法最大乘积：1:最小次小最大 2：最大次大次次大，所以题目就编程要找出这五个数字，那么找的方法有先排序再找，还有遍历一遍找，题目中要求时间复杂度为O(n),那就不能用排序再找的方法，只能有遍历法找。

代码实现

import java.util.*;


public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        // 该题的测试用例：[2,5,3,1]  [-8,-2,-5,-1] [-5,-1,6,3][-3,-1,5,0,2]
        //[-1,5,0,2]，还有要注意当乘积超过int的时候应该用long来存结果，通过分析可得知，这些组合中智存在两种计算方法最大乘积：
        //1:最小*次小*最大  2：最大*次大*次次大
        //所以题目就编程要找出这五个数字，那么找的方法有先排序再找，还有遍历一遍找，题目
        //中要求时间复杂度为O(n),那就不能用排序再找的方法，只能有遍历法找。
        if(A.length<4){
            return A[0]*A[1]*A[2];
        }
        
        int min1=Integer.MAX_VALUE,min2=Integer.MAX_VALUE,max1=Integer.MIN_VALUE
            ,max2=Integer.MIN_VALUE,max3=Integer.MIN_VALUE;
        
        for(int a:A){
            if(a<min1){
                min2=min1;
                min1=a;
            }else if(a<min2){
                min2=a;
            }
            
            if(a>max1){
                max3=max2;
                max2=max1;
                max1=a;
            }else if(a>max2){
                max3=max2;
                max2=a;
            }else if(a>max3){
                max3=a;
            }
        }
        
        return Math.max((long)min1*min2*max1,(long)max1*max2*max3);
    }
}