O(n) runtime, O(1) memory Python solution


  • 0
    J

    The key intuition is that one of the trade must involve the highest price.

    Step 1:

    Calculate the global best trade. Note the trade sequence is prices [i,j].

    Note that the highest price is j

    Step 2:

    If it is the first trade, then the second trade profit is calculated by prices[j+1:]

    If it is the second trade, then there are two options:

    (1) the first trade happens before the current best trade, calculate the profit by prices[0:i]

    (2) the first trade happens within the current trade. The key intuition here is that the profit must be the maximum running loss. It can be calculated by reverse the price sequence, aka prices[j,i,-1]

    I am sure my code can be improved upon. As it stands, it beats 73%

    class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        
        # Since there are at most two trades, the trade must happen at two non-overlapping period
        # therefore, such scheme must maximize the profit over two period.
        
        # Method 1:
        # cut the history by 2: n-1 ways
        # within each segment, apply the one trade algorithm
        # Runtime is O(n^2), memory O(1)
        # Too costly, run time out
        #################################################
        # Method 2:
        # One trade must involve sell on the highest price.
        
        # if it is the first trade, split the history from there
        # if it is the second trade, find the largest cumulative loss in the single trade, and the profit will be profit + cumulative loss
        # the largest loss can be found by reversing the sequence of prices
        
        # Runtime O(n), memory O(1)
        # 73%
        
        def best_trade(prices):
            if prices == []:
                return 0,[]
            
            profit = 0
            book = 0
            
            # need to code the start and end idx
            trade_idx = [0,1]  # start & end
            best_trade_idx = [0,0]
            best_profit = 0
    
                        
            T = len(prices)
            for i in range(T-1):
                delta = prices[i+1] - prices[i]
                if book + delta <0:
                    # switch position if the cost basis becomes negative
                    # reset book and start_idx
                    profit = max(book,profit)
                    # update the best history
                    trade_idx[1] = i
                    if profit > best_profit:
                        best_trade_idx = [x for x in trade_idx]
                        best_profit = profit
                    # start anew
                    book = 0
                    trade_idx = [i+1,i+1]
                else:
                    book += delta
                    if book >= profit:
                        trade_idx[1] = i+1
                        profit = book
                    # check if the current trade is the best trade
                    if profit > best_profit:
                        best_trade_idx = [x for x in trade_idx]
                        best_profit = profit
    
            return profit, best_trade_idx
        
        
        ##############################
        # deal with outlier
        n = len(prices)
        if n<=1:
            return 0
            
        # establish one trade baseline
        base_profit, trade_idx = best_trade(prices) 
        max_idx = trade_idx[1]
        
    
        
        if max_idx != n:
            second_trade_bonus,_ =  best_trade(prices[max_idx+1:])
        else:
            second_trade_bonus = 0
            
        # case 2: second trade
        trade_seq = prices[trade_idx[0]:(max_idx+1)] 
        
        # first trade could be before the best trade
        first_trade_bonus_b,_ = best_trade(prices[:trade_idx[0]])
        # first trade could be within the best trade
        trade_seq.reverse()
        first_trade_bonus_w,_ = best_trade(trade_seq)
        first_trade_bonus = max(first_trade_bonus_b, first_trade_bonus_w)
    
        return base_profit + max(first_trade_bonus,second_trade_bonus)

Log in to reply
 

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