2 lines Python via sorting


  • 0

    First we sort the array A. After sorting, if A[0] >= 0 or A[-1] <= 0, we know the answer is A[-3]*A[-2]*A[-1]. Otherwise, when A[0] < 0 < A[-1], we consider two sub-situations A[0]*A[1]*A[-1] and A[0]*A[1]*A[2] which depends on whether A[-1] is positive or not.

    class Solution(object):
        def maximumProduct(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            A.sort()
            return max(A[-3]*A[-2]*A[-1], A[0]*A[1]*A[-1])
    

  • 0

    @realisking said in 2 lines Python via sorting:

    A[0]*A[1]*A[2]

    Can you give an example where this would be needed?


  • 0

    @StefanPochmann
    Aha, here is my thinking process. When A[0] < 0 < A[-1], we know A[-1] is the maximum positive number and A[0] is the minimum negative number in the array. Then, if A[1] is negative, one possible answer can be A[0] * A[1] * A[-1].

    And for the case when A[1] is positive, A[0] * A[1] is negative and we wanna keep the three number product as small as possible by multiply another smallest number A[2]. For example, the sorted A is [-1,1,2].

    Wait a second, the example above actually within the answer A[-3]*A[-2]*A[-1]... Why are you so smart, Stefan.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.