三个数的最大乘积。采用线性扫描方法。

三个数的最大乘积

整形数组nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。

备注：乘积不会越界

示例：

1输入：[-3, -2, -1, 4, 5, 6]
2输出：120

思路

则个题目其实就是线性扫描求最大值。

  • 如果都是正数，那么正数的最大三个值相乘即可。
  • 如果存在正数和负数，那么最大值，必须有两个负数，那么转化为两个最小的负数和一个最大的正数。
  • 比较三个最大正数的的乘积和两个最小负数与最大正数的乘积的大小

可以直接通过排序的方式，找到最大值和最小值，时间复杂度o(nlogn)

也可以通过遍历，每次更新这五个数的大小，时间复杂度为o(n)

解题

1//排序法
2public static int sort(int[] nums)
3{
4    Arrays.sort(nums);
5    int n = nums.length;
6    return Math.max(nums[0] * nums[1] * nums[n - 1],
7                    nums[n -1] * nums[n - 2] * nums[n - 3]);
8}

或者

 1//最大最小值法
 2public static getMaxMin(int[] nums)
 3{
 4    int min1 = Integer.MAX_VALUE;
 5    int min2 = Integer.MAX_VALUE;
 6    int max1 = Integer.MIN_VALUE;
 7    int max2 = Integer.MIN_VALUE;
 8    int max3 = Integer.MIN_VALUE;
 9    
10    for(int x : nums)
11    {
12        if(x < min1)
13        {
14            min2 = min1;
15            min1 = x;
16        }else if(x < min2)
17        {
18            min2 = x;
19        }
20        
21        if(x > max1)
22        {
23            max3 = max2;
24            max2 = max1;
25            max1 = x;
26        }else if(x > max2)
27        {
28            max3 = max2;
29            max2 = x;
30        }else if(x > max3)
31        {
32            max3 = x;
33        }
34    }
35    
36    return Math.max(min1 * min2 * max1,
37                    max1 * max2 * max3);
38}