NC106 三个数的最大乘积

描述

给定一个长度为  的无序数组 

正在上传…重新上传 ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度：  ，空间复杂度： 

正在上传…重新上传取消 。

数据范围：

3 \le n \le 2 * 10^53≤n≤2∗105

-10^6 \le A[i] \le 10^6−106≤A[i]≤106

示例1

输入：

[3,4,1,2]

复制返回值：

24

复制

1、如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
2、如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
3、综上，在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。

图解：

 直接排序可以找到关键的5个值

不排序也可以通过直接遍历找个5个关键值

import java.util.*;
public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        // write code here
        // 最小的和第二小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 最大的、第二大的和第三大的
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        // 顺序遍历查找最小的两个数、最大的三个数
        for(int i = 0;i < A.length;i ++){
            if(A[i] < min1){//更新最小值
                min2 = min1;
                min1 = A[i];
            }else if(A[i] < min2){//更新第二小
                min2 = A[i];
            }
            if (A[i] > max1){//更新最大值
                max3 = max2;
                max2 = max1;
                max1 = A[i];
            }else if(A[i] > max2){//更新第二大
                max3 = max2;
                max2 = A[i];
            }else if(A[i] > max3){//更新第三大
                max3 = A[i];
            }
        }
        return Math.max((long)min1 * min2 * max1,(long) max1 * max2 * max3);
    }
}