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


  • 0
    H

    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
    

Log in to reply
 

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