MaximumProductOfThreeNumbersOPT [source code]

public class MaximumProductOfThreeNumbersOPT {
    public int maximumProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE, 
            max2 = Integer.MIN_VALUE, 
            max3 = Integer.MIN_VALUE, 
            min1 = Integer.MAX_VALUE, 
            min2 = Integer.MAX_VALUE;

        for (int n : nums) {
            if (n > max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n > max2) {
                max3 = max2;
                max2 = n;
            } else if (n > max3) {
                max3 = n;
            }

            if (n < min1) {
                min2 = min1;
                min1 = n;
            } else if (n < min2) {
                min2 = n;
            }
        }

        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }

    public static void main(String[] args) {
        MaximumProductOfThreeNumbersOPT tester = new MaximumProductOfThreeNumbersOPT();
        int[] input1 = {-1000, -1000, -1000};
        assert tester.maximumProduct(input1) == -1000_000_000;
        int[] input2 = {1,2,3};
        assert tester.maximumProduct(input2) == 6;
        int[] input3 = {-1,-2,-3};
        assert tester.maximumProduct(input3) == -6;
        int[] input4 = {-1,-2,-3,-4,-5,1,2,3};
        assert tester.maximumProduct(input4) == 60;
        // System.out.println(tester.maximumProduct(input1));
    }
}

这个是 submission 最优解, 15ms, 90%;

这个算法很有教育意义, 因为这个算法是正儿八经可以通过研究naive 算法, 也就是我前面算法的优化得到的. 首先, 一个sorting, 这个肯定对这个问题是一个 overkill. 我们的想法肯定是写一个新算法, 但是不依赖 sorting, 但是我们需要什么 sorting 可以提供的信息呢? 这个算法其实就提供了一个解答, 虽然我们对 nums 整个进行了一个 sort, 但是实际上真正被我们 access, 或者所有可能被我们 access 的只有五个 element, 最小的两个和最大的三个. 既然如此, 我们只要一个1pass, 然后把这三个都保存下来就行了.

注意因为这里涉及到不仅是第一名的保存, 而是前三名的保存, 在更新的时候要涉及到一个类似 shift 的操作;
另外这里他们的做法对于正负号没有进行纠结, 类似 DP 的思路, 你不需要管这些细节, 因为你最后需要的只是一个最值;

Problem Description

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
The length of the given array will be in range [3,10^4] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
Difficulty:Easy
Category:Algorithms
Acceptance:46.18%
Contributor: lingvisa
Companies
intuit
Related Topics
array math
Similar Questions
Maximum Product Subarray