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)
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.
In addition to the @David Eisenstat answer, few additional comments:
Noneas 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.
0x7FFFFFFF would be the equivalent to the max signed int,
sys.maxsize == 0x7FFFFFFF
In python2 you can make the next comparisons, both
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 :)
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 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
pc. The author could have used -1000 instead.
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