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- prices) # do as much as possible buyq, sellq = ,  buy, sell = prices, 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 - buyq for i in range(len(buyq)-1): if sellq[i] - buyq[i+1] < cur: cur = sellq[i] - buyq[i+1] idx = i cur2 = sellq - buyq 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
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.