Preface explains

Algorithm learning, daily brush record.

Subject to connect

The largest product of three numbers

The subject content

Given an integer array nums, find the largest product of three numbers in the array and print the 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

Tip:

3 <= nums.length <= 10^4

-1000 <= nums[i] <= 1000

The analysis process

It is analyzed in three cases.

In the first case, all positive numbers, the maximum product is equal to the first maximum times the second maximum times the third maximum.

In the second case, it’s all negative, the maximum product is equal to the first maximum times the second maximum times the third maximum.

In the third case, there are positive and negative numbers, and the maximum product is one of the two cases, the maximum.

1, maximum product = the first maximum * second maximum * third maximum, take the maximum is three numbers, this situation is very well understood, I will not go into detail here.

2, the largest product = first minimum second minimum * * the first maximum, this kind of situation is that the absolute value of the minimum side is bigger than the maximum side, so take the minimum two side of the minimum value, because the two negative multiplication is positive, so take only the first minimum value and the minimum value, maximum times first.

So first sort the array NUMs, get the first minimum, second minimum, first maximum, second maximum, third maximum, calculate the product of the above two cases, take the maximum is the answer.

To solve the code

Class Solution {public int maximumProduct(int[] nums) {sort(nums); Int min1 = nums[0]; Int min2 = nums[1]; Int max1 = nums[nums.length-1]; Int max2 = nums[nums.length-2]; Int max3 = nums[nums.length-3]; // If all positive numbers are positive, the maximum product = first maximum * second maximum * third maximum // If all negative numbers are negative, the maximum product = first maximum * second maximum * third maximum // If both positive and negative numbers are negative, the maximum product is one of the following two cases, take the maximum // the first case, Int product1 = max1 * max2 * max3; Int product2 = min1 * min2 * max1; int product2 = min1 * min2 * max1; Return math. Max (product1, product2); }}Copy the code

Submit the results

It took 12ms to execute, beating 70.88% of users in time, 39.9MB in memory consumption, and 37.04% in space.

The original link

The largest product of three numbers