Maximum Product of Three Numbers

Question

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)

Answer 1

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.

Answer 2

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