Python AC with 63ms,DP and not DP


  • 2
    S

    simply track the negtives and 0s ,and the index of A,not DP

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def maxProduct(self, A):
            def prod(A):
                sum_ = 1
                for i in A: sum_ *= i
                return sum_
                
            len_ = len(A)
            if len_ == 1: return A[0]
            a = []
            b = []
            for i,x in enumerate(A):
                if x == 0 : a.append(i)
                if x < 0  : b.append(i)
            len_b = len(b)
            len_a = len(a)
            if len_a == 0:
                if len_b % 2 ==0:
                    return prod(A)
                else:
                    return max( prod(A[0:b[len_b -1]]),  prod(A[b[0] + 1:]) )
            else:
                max_ = self.maxProduct( A[a[len_a-1] + 1 :])  if  A[a[len_a-1] + 1:]  else A[0]
                head = 0
                for i in a:
                    max_ = max(self.maxProduct( A[head:i]), max_ )  if  A[head:i]  else max_
                    head = i
                return max(max_, 0)
    

    and in DP way:

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def maxProduct(self, A):
            max_, min_, res= A[0], A[0], A[0]
            for i in range(1,len(A)):
                max_tmp = max_
                max_ =  max( max_tmp * A[i], A[i], min_ * A[i] )
                min_ =  min( max_tmp * A[i], A[i], min_ * A[i] )
                if max_ > res: res = max_
            return res

Log in to reply
 

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