MaximumProductOfThreeNumbers2 [source code]

public class MaximumProductOfThreeNumbers2 {
    public int maximumProduct(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int resP = Integer.MIN_VALUE, resN = Integer.MIN_VALUE;
        if (nums[n - 3] >= 0 || nums[n - 1] >= 0 && nums[1] <= 0) {
            resP = nums[n - 1] * nums[n - 2] * nums[n - 3];
            resN = nums[0] * nums[1] * nums[n - 1];
        } else {
            resP = 1;
            for (int i = n - 1; i >= n - 3 && i >= 0; i--) resP *= nums[i];
        }
        return Math.max(resP, resN);
    }

    public static void main(String[] args) {
        MaximumProductOfThreeNumbers2 tester = new MaximumProductOfThreeNumbers2();
        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));
    }
}

这里把代码的逻辑简化了了一下;
前面的逻辑是根据 nums 被 sort 之后具体的细致的正负分布来做, 这里直接按照最后 product 的正负来区分. 如果能够取到正值, 那么就进入第一个 branch; 否则就进入第二个 branch.
注意第一个 branch 里面的时候, P 和 N 都要更新, again, 这两个之间一定要有一个比较;
第二个 branch 里面的 for 的 header 有两个terminating condition, 因为我们这里的判断用的是带有等号的, 所以实际上可能有比如[0]这样的, 长度根本不到3, 所以要保证 i 不能过界.

奇怪的是这样改了之后速度居然降低了, 34ms, 46%.

34 46

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