MaximumProductOfThreeNumbers [source code]

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

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

这个题目总体还是简单的, 直接想要 stream 算法或者历史信息类的题目来做, 但是没有想到什么特别好的办法, 所以就简化难度, 先 sort. sort 之后无非就是分情况讨论;
最大的product 要么是三个正数相乘, 要么是两负一正. 两负一正的这个很好判断, 单独一个 if 就可以判断. 三正这个判断就稍微复杂一点;

速度是31ms, 75%, 凑合;

我一开始犯了一个错误是认为只要有一个 resP 就够了, 因为两负一正的情况也可以包含在 resP 的情况下. 但是我忽视一个问题, 两负一正和三正是可能同时存在的, 如果不进行比较就不知道两者之间究竟谁是真正的 max;

这里刚开始失败几次的一个问题是对于两个 res 的 init 太草率了. 先是都给的1, 但是这个明显有问题(后面有一个 max); 然后给的-1000, 因为是给出的domain 下限, 以为没问题了, 但是 input1这个的存在, 就是为了故意 break 这种 init 的.

另外,对于32位的 Integer 的最大最小值, 也就是最大绝对值的大小, 要有一个大概的印象, 知道是2开头, 然后后面有9位就行了,也就是2b 多一些;

刚开始还有一个错误就是把^当做 power 用了. 在 JAVA 里面^不是 power, ^必须用专门的Math.pow(n,2)这样的方式来写;

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