Maximum Product of Three Numbers

https://leetcode.com/problems/maximum-product-of-three-numbers/description/

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

Thoughts

最大的乘积要不就是三个正数, 要不就是俩负一正. 前者直接取最大的三个数, 后者取最小的两个数和最大的一个数.

Code

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

Analysis

O(nlgn)用于排序. 也可以O(N)来找多次最大或最小.