628. Maximum product of three numbers

Address ：

Power button https://leetcode-cn.com/problems/maximum-product-of-three-numbers/

subject ：

Here's an integer array nums , Find the largest product of three numbers in the array , And output this product .

Example 1：

Input ：nums = [1,2,3] Output ：6

Example 2：

Input ：nums = [1,2,3,4] Output ：24

Example 3：

Input ：nums = [-1,-2,-3] Output ：-6

Tips ：

3 <= nums.length <= 104 -1000 <= nums[i] <= 1000

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximum-product-of-three-numbers
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

1. All positive numbers , Take the three largest numbers

2. All negative numbers , There will be no positive results , Also take the three largest numbers

3. There are positive and negative

        3.1 Only 1 Negative numbers         Take the three largest numbers

        3.2 redundant 2 Negative numbers         2 Maximum negative numbers + Maximum integer , Three largest integers , Taking the maximum

So the last thing is to see which is the maximum ：

Minimum two numbers + The maximum number , Three maximum numbers

Method 1 、 Sort

#define max(a,b) ( (a) > (b) ? (a) : (b) )

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int maximumProduct(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);

    return max(nums[0] * nums[1] * nums[numsSize-1], nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3]);
}

Method 2 、 Linear search

Sorting is lossy , If you can find what you need without sorting 5 Elements ：2 Minimum ,3 The biggest

Then the performance will be improved

The title gives a numerical range ：-1000 <= nums[i] <= 1000

So it can be assumed that ：

1. The minimum value is initialized to 1000（ Maximum ）

2. The maximum value is initialized to -1000（ minimum value ）

If you find something smaller than the minimum value during traversal , Then update the minimum ; Similar to several other elements

#define MAXVALUE 1000
#define MINVALUE -1000

#define max(a,b) ( (a) > (b) ? (a) : (b) )

int maximumProduct(int* nums, int numsSize){
    int min1 = MAXVALUE, min2 = MAXVALUE;
    int max1 = MINVALUE, max2 = MINVALUE, max3 = MINVALUE;

    for(int i=0; i<numsSize; i++)
    {
        if(min1 > nums[i])
        {
            min2 = min1;
            min1 = nums[i];
        }
        else if(min2 > nums[i])
        {
            min2 = nums[i];
        }

        if(max1 < nums[i])
        {
            max3 = max2;
            max2 = max1;
            max1 = nums[i];
        }
        else if(max2 < nums[i])
        {
            max3 = max2;
            max2 = nums[i];
        }
        else if(max3 < nums[i])
        {
            max3 = nums[i];
        }
    }

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

The method of linear search should be mastered

See more brush notes