Python DP and Non-DP solution


  • 0
    Y

    DP solution, time 104ms

    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            if(len(prices)<=1): return 0
            b1=-prices[0]
            s1=0
            b2=-prices[0]
            s2=0
            for i in xrange(1,len(prices)):
                p=prices[i]
                s2=max(s2,b2+p)
                b2=max(b2,s1-p)
                s1=max(b1+p,s1)
                b1=max(b1,-p)
                
            return max(s1,s2)
    

    Non-DP solution, 88ms

    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            if(len(prices)<=1): return 0
            minb=prices[0]
            mini=0
            for i in xrange(1,len(prices)):
                p=prices[i]
                if(p<=minb):
                    minb=p
                    mini=i
                else:
                    break
            #print minb,mini
            trans2m=0
            fixi=mini
            listr=[]
            i=fixi+1
            while(i>fixi and i<len(prices)):
                p=prices[i]
                if(p>minb): 
                    i=i+1
                    continue
                #find partial max
                dictr=self.maxPartial(prices,mini,i)
                #print dictr
                if(1 in dictr):
                    if(dictr[1]>trans2m):
                        trans2m=dictr[1]
                listr.append(dictr[0][0])
                if(len(dictr[0])>1): listr.append(dictr[0][1])
                minb=p
                mini=i
                i=i+1
            #consider the last min piece
            dictr=self.maxPartial(prices,mini,i)
            #print dictr
            if(1 in dictr):
                if(dictr[1]>trans2m):
                    trans2m=dictr[1]
            listr.append(dictr[0][0])
            if(len(dictr[0])>1): listr.append(dictr[0][1])
            max1=0
            max2=0
            for pr in listr:
                if(pr>max1):
                    max2=max1
                    max1=pr
                elif(pr>max2):
                    max2=pr
                  
            #print trans2m
            #print listr
            return max(max1+max2,trans2m)
        
        def maxPartial(self,prices,i,j):
            minp=prices[i]
            maxp=prices[i]
            indexm=i
            d={}
            for k in xrange(i,j):
                if(prices[k]>maxp):
                    maxp=prices[k]
                    indexm=k
            if(indexm==i):
                d[0]=[0]
                return d
            #print "max index: ",indexm
            list1=[i,i]
            list2=[i,i]
            d[0]=[maxp-minp]
            if(indexm+1<j-1): 
                list2=self.getMaxInc(prices,indexm+1,j)
                if(list2[0]!=list2[1]):
                    d[0].append(prices[list2[1]]-prices[list2[0]])
                    
            if(i+1<indexm-1): 
                list1=self.getMaxDrop(prices,i+1,indexm)
                if(list1[0]!=list1[1]):
                    trans2=prices[list1[0]]-minp+maxp-prices[list1[1]]
                    if((maxp-minp+prices[list2[1]]-prices[list2[0]]) < trans2):
                        d[1]=trans2
            return d
            
        def getMaxInc(self,prices,i,j):
            maxt=0
            mina=prices[i]
            minai=i
            index1=i
            index2=i
            for k in xrange(i,j):
                if(prices[k]<mina):
                    mina=prices[k]
                    minai=k
                elif(prices[k]-mina>maxt):
                    maxt=prices[k]-mina
                    index1=minai
                    index2=k
            return [index1,index2]
            
        def getMaxDrop(self,prices,i,j):
            maxt=0
            maxa=prices[i]
            maxai=i
            index1=i
            index2=i
            for k in xrange(i,j):
                if(prices[k]>maxa):
                    maxa=prices[k]
                    maxai=k
                elif(maxa-prices[k]>maxt):
                    maxt=maxa-prices[k]
                    index1=maxai
                    index2=k
            return [index1,index2]
    

Log in to reply
 

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