I just directly convert the problem to max sum of k subarray, and merge the neaby profit, if there are the same positive or negative, and remove the 0 profit. Until the list is one positive with one negative. if the first and last profits is negative, it will not be considered. so just remove it. i just assume there is enough transactions. so the max. profit is the sum of all positive. if there less transactions, we have two choice merge two transactions or drop one transation, so how to choice? compare the cost of two operations, we drop the min positive profit or merge the max negative profit with it's nearby positive profit. the cost is -profit, profit.
after calculate the profit, we get [2, -5, 3, -2, 3] and we should reduce one operation.
The min. positive profit is 2
The max. neg. profit is -2
so is the same drop or merge
if drop 2, we get [3, -2, 3], the max. profit is 3+3=6
if merge -2, we get[2, -5, 4], the max. profit is 2+4=6
class Node(): def __init__(self, val): self.val = val self.pre = None self.nxt = None class Solution(object): def maxProfit(self, k, prices): """ :type k: int :type prices: List[int] :rtype: int """ n = len(prices) if n < 2 or not k: return 0 # change the prices to the profits # profits in the format of positive with negative # e.g. 3, -2, 5, -5, 7 profits =  current_profit = prices - prices transactions = 0 for i in range(2, n): profit = prices[i] - prices[i-1] if profit == 0 or current_profit == 0 or \ profit > 0 and current_profit > 0 \ or profit < 0 and current_profit < 0: current_profit += profit else: if profits or current_profit > 0: profits.append(current_profit) if current_profit > 0: transactions += 1 current_profit = profit if current_profit > 0: profits.append(current_profit) transactions += 1 # create the double link of the profits, del. and create O(1) # build the positive and negative profits heapq root = Node(0) prenode = root pos_heapq, neg_heapq = ,  for p in profits: node = Node(p) prenode.nxt, node.pre = node, prenode prenode = node if p > 0: heapq.heappush(pos_heapq, [p, node]) else: heapq.heappush(neg_heapq, [-p, node]) times = max(transactions-k, 0) # delete the root node if root.nxt: root.nxt.pre, root = None, root.nxt # the max profit is sum of positive profits # but the transaction is limit by k # so there are two operations of transactions # merge the two nearby transactions or # delete one transactions # choose the min. cost, which means the min. profit of positive # or the max. profit of negative, using the lazy delete for heapq while times: if pos_heapq > neg_heapq: val, node = heapq.heappop(neg_heapq) if node.val == -val: times -= 1 new_val = node.pre.val + node.nxt.val + node.val new_node = Node(new_val) new_node.pre = node.pre.pre if node.pre.pre: node.pre.pre.nxt = new_node new_node.nxt = node.nxt.nxt if node.nxt.nxt: node.nxt.nxt.pre = new_node # lazy delete node.pre.val = node.nxt.val = 0 heapq.heappush(pos_heapq, [new_val, new_node]) else: val, node = heapq.heappop(pos_heapq) if node.val == val: times -= 1 if not node.pre: node.nxt.val = 0 elif not node.nxt: node.pre.val = 0 else: new_val = node.pre.val + node.nxt.val + node.val new_node = Node(new_val) new_node.pre, node.pre.pre.nxt = node.pre.pre, new_node new_node.nxt, node.nxt.nxt.pre = node.nxt.nxt, new_node node.pre.val = node.nxt.val = 0 heapq.heappush(neg_heapq, [-new_val, new_node]) max_profit = 0 while pos_heapq: val, node = heapq.heappop(pos_heapq) if val == node.val: max_profit += val return max_profit