# Python Solution with O(min(nlgn, klgn)) time my easy directly thinking

• 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
``````

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