首页 > itarticle > 【leetcode】628. maximum product of three numbers

【leetcode】628. maximum product of three numbers

admin 11月 13, 2020 0

Description

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

Example

Input: [1,2,3]
Output: 6

Note

1.The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2.Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

Solution

public int (int[] nums) {
        Arrays.sort(nums);
        int posNum = 0;
        int negNum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                posNum++;
            }
            if (nums[i] < 0) {
                negNum++;
            }
        }
        int len = nums.length;
        if (len == 3) {
            return nums[0] * nums[1] * nums[2];
        }
        if (nums[0] > 0 || negNum < 2) {
            return nums[len - 1] * nums[len - 2] * nums[len - 3];
        }
        if (negNum >= 2 && posNum <= 2) {
            return nums[0] * nums[1] * nums[len - 1];
        }
        if (negNum == 2 && posNum > 2) {
            int negProduct = nums[0] * nums[1];
            int posProduct = nums[len - 1] * nums[len - 2];
            return nums[len - 3] * Math.max(negProduct, posProduct);
        }
        if (negNum > 2 && posNum > 2) {
            return Math.max(nums[0] * nums[1] * nums[len - 1], nums[len - 1] * nums[len - 2] * nums[len - 3]);
        }
        return 0;
    }

Result

AC

Analyse

用的很蠢的考虑所有边界情况的方法，没什么问题，就是要注意最后一个条件里的内容判断。

Optimization

public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return Math.max(nums[0] * nums[1] * nums[len - 1], nums[len - 1] * nums[len - 2] * nums[len - 3]);
    }

Analyse

其实思路是一致的。