使用线性扫描算法解决“三个数的最大乘积”问题

题目：三个数的最大乘积
描述：一个整型数组 nums ，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。
注意：乘积不会越界。
重点考察：线性扫描
思路：上一篇我们用排序算法解决了“三个数的最大乘积”问题，但是因为排序的算法复杂度是N*logN，复杂度太高，所以我们需要换一种思路解决问题。从上篇文章我们知道，三个数中：
1、如果数组中全是正数，则排序后最大的三个数相乘即为最大乘积。
2、如果数组中全是负数，则最大的三个数相乘同样也为最大乘积。
3、如果数组中既有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。（例如：[-4,-3,-2,1,4,7]，最大值是 -4 * -3 * 7）
所以，我们得知这道题中最关键的五个数分别是：最大的三个数max1、max2、max3和最小的两个数min1、min2。所以我们要做的事就是找到这五个数，然后按上篇思路在“三个最大正数的乘积”和“两个最小负数与最大正数的乘积”两个数之间取最大值即可。

package od;

/**
 * 三个数的最大乘积
 * 一个整型数组 nums ，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。
 * 注意：乘积不会越界。
 * 重点考察：线性扫描
 * 原文地址：https://www.codernav.com/2821.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest21 {
    public static void main(String[] args) {
        int num = f(new int[]{-4, -3, -2, 1, 4, 7, 9});
        System.out.println(num);
        int num1 = f(new int[]{1, 2, 3, 4, 5, 6});
        System.out.println(num1);
    }

    private static int f(int[] nums) {
        // 最小的和第二小的
        int min1 = 0, min2 = 0;
        // 最大的、第二大的和第三大的
        int max1 = 0, max2 = 0, max3 = 0;
        for (int x : nums) {
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = 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(max1 * max2 * max3, min1 * min2 * max1);
    }

}