Python DP solution O(k*n) time, O(k) space


  • 0
    Y

    I haved added a pre-process function to get rid of unnecessary elements.
    For k greater than n/2, quickly return the maximum profit one can get

    class Solution(object):
        def maxProfit(self, k, prices):
            """
            :type k: int
            :type prices: List[int]
            :rtype: int
            """
            if(len(prices)<=1 or k==0 ): return 0
            if(len(prices)==2): return max(0,prices[1]-prices[0])
            #print len(prices)
            prices=self.preProcess(prices)
            if(len(prices)<=1 or k==0 ): return 0
            #return 0
            k=min(k,len(prices)/2)
            if(k==len(prices)/2): return self.getMaxP(prices)
            b=k*[-prices[0]]
            s=k*[0]
            ktmp=1
            for i in xrange(1,len(prices)):
                p=prices[i]
                j=ktmp
                while(j<k and b[j]!=-prices[0]): j=j+1
                j=min(j,k-1)
                ktmp=j
                while(j>=1):
                    s[j]=max(s[j],b[j]+p)
                    b[j]=max(b[j],s[j-1]-p)
                    j=j-1
                s[0]=max(s[0],b[0]+p)
                b[0]=max(b[0],-p)
                #print s
            return max(s)
            
        def preProcess(self,prices):
            newp=[]
            p0=prices[0]
            for i in xrange(1,len(prices)):
                if(prices[i]<=p0): 
                    p0=prices[i]
                else: break
            if(i==len(prices)): return newp
            
            j=i
            prev=prices[j]
            for j in xrange(i+1,len(prices)):
                p=prices[j]
                if(p<p0 and prev==p0):
                    p0=p
                    prev=p
                elif(p<prev):
                    newp.append(p0)
                    newp.append(prev)
                    p0=p
                    prev=p
                else: prev=p
            if(prev>p0):
                newp.append(p0)
                newp.append(prev)
            return newp
            
        def getMaxP(self,prices):
            maxp=0
            for i in xrange(0,len(prices)-1):
                if(i%2==0): maxp=maxp-prices[i]
                else:maxp=maxp+prices[i]
            if((len(prices)-1)%2==1): maxp=maxp+prices[-1]
            return maxp
    

Log in to reply
 

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