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.

e.g.

input:

2

[3,3,5,0,0,3,1,4]

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[1] - prices[0]
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[0] > neg_heapq[0]:
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
```