# Maximum Product of Three Numbers

7

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

3

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.

3

• 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 :)

2

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.

-1

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:

``````>>> 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.

User contributions licensed under CC BY-SA 3.0