Simplified AC Python


  • 1
    B
    class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        if not A:
            return 0
        elif len(A)==1:
            return A[0]
    
    # need max and min together
    
        maxnum=A[0]
        minnum=A[0]
    
        resultmax=maxnum
    
        for i in range(1,len(A)):
            if A[i]>0:
                maxnum=max(A[i],A[i]*maxnum)
                minnum=min(A[i],A[i]*minnum)
            else:
                oldmax=maxnum
                maxnum=max(A[i],A[i]*minnum)
                minnum=min(A[i],A[i]*oldmax)
    
            resultmax=max(resultmax,maxnum)
    
        return resultmax
    

    this has been simplified from a full DP with arrays storing max and min ending at each i


  • 0
    L

    Thank you for posting your solution. It very easy to understand and the algorithm works great.
    BTW, python alow multiple assignment. Thus you can use maxnum,minnum=max(A[i],minnumA[i]),min(A[i],maxnumA[i]) instead to get rid of the oldmax variable.


Log in to reply
 

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