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(nlogn)O(n\log{n})

Space Complexity: O(1)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])

Last updated