Maximum Product of Three Numbers

Question

Maximum Product of Three Numbers

I am trying to solve this problem from leetcode, going to copy here for convenience

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,104] 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.

After (unsuccessfully) trying it, I googled the solution and this works

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = pa = pb = pc = None
        na = nb = 0x7FFFFFFF
        for n in nums:
            if n > pa:
                pa, pb, pc = n, pa, pb
            elif n > pb:
                pb, pc = n, pb
            elif n > pc:
                pc = n
            if n < na:
                na, nb = n, na
            elif n < nb:
                nb = n
        return max(ans, pa * na * nb, pa * pb * pc)

I understand the logic except why na and nb are assigned a value of 0x7FFFFFFF. It looks like it is int32's maximum value. Can someone help me explain the significance of this number and why it is used here? (I would have used 1001 instead)

python

algorithm

python-2.7

asked on Stack Overflow May 10, 2018 by

user1596115 • edited May 10, 2018 by

Patrick Haugh

4 Answers

In pseudocode, 0x7FFFFFFF would be rendered as infinity (and None, as minus infinity). The proof of correctness is a lemma to the effect that the three numbers with the greatest product can be found among the greatest three and the least two. Plus/minus infinity serves as a sentinel value for the min/max two/three values, to be replaced shortly by actual values once the first three have been scanned.

1001 would work as well.

answered on Stack Overflow May 10, 2018 by

David Eisenstat

In addition to the @David Eisenstat answer, few additional comments:

Considering None as minus infinity is something that will work on python2 but it'll raise an exception in python3, for instance:

In early Python, the decision was made that the comparison of any two objects was legal and would return a consistent result. So objects of different types will compare according to an ordering on their types (an implementation dependent, unspecified, but consistent ordering), and objects of the same type will be compared according to rules that make sense for that type.

Other implementations have the right to compare an integer and None differently, but on a specific implementation, the result will not change.

Python 3 will raise an exception on such comparisons.

You're correct, 0x7FFFFFFF would be the equivalent to the max signed int, sys.maxsize == 0x7FFFFFFF
In python2 you can make the next comparisons, both 0x7FFFFFFF>(1000*1000*1000) and None<-(1000*1000*1000) are True, so using 0x7FFFFFFF as upper bound and None as lower bound is just fine, although other bounds would be correct as well
That said, I'd suggest you refactor that code to make it work also in python3 :)

answered on Stack Overflow May 10, 2018 by

BPL

Taking the following example: [-999, -999, 100, 200, 300], the answer is to take -999, -999 and 300 (and not simply the product of the 3 largest numbers).

As a consequence, you need to store:

the 3 largest numbers (pa, pb, pc)
the 2 smallest numbers (na, nb)

The result is the greatest value between pa * na * nb and pa * pb * pc.

0x7FFFFFFF is just a very big number used to find the smallest values. Since the greatest possible value is 1000, 1000 could have been used instead.

Similarly, the author used None to initialize pa, pb and pc. The author could have used -1000 instead.

answered on Stack Overflow May 10, 2018 by

Maxime Chéramy

Although this doesn't actually provide an answer to the actual question, it's an alternative that goes around the scenario that was brought up, and achieves the same (final) goal (it's more elegant, but slower - especially for large lists).
It works on both Python 2 and Python 3 (where reduce could also be replaced by itertools.accumulate), and makes use of:

[Python 2.Docs]: Built-in Functions (max, reduce)
[Python 2.Docs]: operator - Standard operators as functions (mul)
[Python 2.Docs]: itertools - Functions creating iterators for efficient looping (combinations)

>>> import itertools
>>> import operator
>>> 
>>> l = [1, 9, 0, -5, 7, 2, 4]
>>>
>>> def max_prod(seq, count=3):
...     return max(reduce(operator.mul, item) for item in itertools.combinations(seq, count))
...
>>> max_prod(l)
252

which is: 9 * 7 * 4.

answered on Stack Overflow May 10, 2018 by

CristiFati • edited Oct 22, 2020 by

CristiFati

User contributions licensed under CC BY-SA 3.0