628_Maximum Product of Three Numbers

[easy] [array, math]

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

Solution:

Idea:

The maximum can be achieved by multiplying the largest 3 positive values or multiplying the largest 1 positive values and the smallest 2 negative values.

Time Complexity: $O(n\log{n})$

Space Complexity: $O(1)$

def maximumProduct(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])

Previous504_Base 7 NextMultiply Two Integers

Last updated 4 years ago

Solution:

Idea:

The maximum can be achieved by multiplying the largest 3 positive values or multiplying the largest 1 positive values and the smallest 2 negative values.

Time Complexity:

O(n\log{n})

Space Complexity:

O(1)

def maximumProduct(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])