Not sure if correct, but is very fast...


  • 0
    R

    Here is the code. The concept is firstly count all possible profitable transaction as much as possible. This will probably higher than k transactions. Then, we merge each two continuous transactions into one step by step. This will reduce the number of transactions. The merged action will guarantee the least lost of profit. Also, it is possible that we drop one transactions. After that, we calculate the total profit.

    class Solution(object):
        def maxProfit(self, k, prices):
    
            if k == 0:
                return 0
            
            if len(prices) < 2:
                return 0
            elif len(prices) == 2:
                return max(0, prices[1]- prices[0])
            
            # do as much as possible
            buyq, sellq = [], []
            buy, sell = prices[0], None
    
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]: # sell
                    sell = prices[i]
                    #previous is buy
                    if buy is not None: 
                        buyq.append(buy)
                        buy = None
                elif prices[i] < prices[i-1]: # buy 
                    buy = prices[i]
                    #previous sell
                    if sell is not None:
                        sellq.append(sell)
                        sell = None
    
            
            if len(buyq) > len(sellq):
                if prices[-1] > buyq[-1]:
                    sellq.append(prices[-1])
                else:
                    buyq.pop()  
            
            if len(buyq) > k:
                res = len(buyq) - k
                for i in range(res):
                    deq(buyq, sellq)        
            total = 0
            for i in range(len(buyq)):
                total += sellq[i] - buyq[i]
            return total
    
    def deq(buyq, sellq):
        idx = 0
        cur = sellq[0] - buyq[1]
        for i in range(len(buyq)-1):
            if sellq[i] - buyq[i+1] < cur:
                cur = sellq[i] - buyq[i+1]
                idx = i
        
        cur2 = sellq[0] - buyq[0]
        idx2 = 0
        for i in range(len(buyq)):
            if sellq[i]-buyq[i] < cur2:
                cur2 = sellq[i]-buyq[i]
                idx2 = i
        
        if cur2 > cur:
            buyq[idx+1] = buyq[idx]
            sellq.pop(idx)
            buyq.pop(idx)
        else:
            sellq.pop(idx2)
            buyq.pop(idx2)
        
        return 
    

  • 0
    R

    Some thought on this problem. 1.Given optimized k+1 transactions (buy and sell), if we only perform k transactions out of it, the final profit should be no larger than what original transactions could get. So profit_k+1 >= profit_k, similarly profit_k >= profit_k-1 etc. That means, given we have an optimized k+1 transactions, we only need to consider k case to reduce, since for any transactions number less than k the profit is smaller than or equal to that of k case. 2. It is very easy to calculate what should do on k transactions (out of k+1 transactions) by eliminating one transaction.


Log in to reply
 

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