628. Maximum Product of Three Numbers

Problem

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.

Problem Summary

Given an integer array, find the maximum product formed by three numbers in the array, and output this product.

Solution Approach

Given an array, find the maximum product that can be formed by choosing any 3 numbers from this array.
The test case data size for this problem is relatively large. If sorting is used, the time complexity is high, so you can directly consider simulation. To choose 3 numbers to form the maximum product, they must be one positive number and two negative numbers, or three positive numbers. Therefore, select the largest three numbers and the smallest two numbers, compare them, and the maximum value can be found. Time complexity O(n)

Code


package leetcode

import (
	"math"
	"sort"
)

// Solution 1: Sorting, time complexity O(n log n)
func maximumProduct(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	res := 1
	if len(nums) <= 3 {
		for i := 0; i < len(nums); i++ {
			res = res * nums[i]
		}
		return res
	}
	sort.Ints(nums)
	if nums[len(nums)-1] <= 0 {
		return 0
	}
	return max(nums[0]*nums[1]*nums[len(nums)-1], nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3])
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// Solution 2: Simulation, time complexity O(n)
func maximumProduct1(nums []int) int {
	max := make([]int, 0)
	max = append(max, math.MinInt64, math.MinInt64, math.MinInt64)
	min := make([]int, 0)
	min = append(min, math.MaxInt64, math.MaxInt64)
	for _, num := range nums {
		if num > max[0] {
			max[0], max[1], max[2] = num, max[0], max[1]
		} else if num > max[1] {
			max[1], max[2] = num, max[1]
		} else if num > max[2] {
			max[2] = num
		}
		if num < min[0] {
			min[0], min[1] = num, min[0]
		} else if num < min[1] {
			min[1] = num
		}
	}
	maxProduct1, maxProduct2 := min[0]*min[1]*max[0], max[0]*max[1]*max[2]
	if maxProduct1 > maxProduct2 {
		return maxProduct1
	}
	return maxProduct2
}