Simple O(n) Python answer


  • 0
    A

    recursively consider three prices position, i, i+1, i+2, if one buy i, one sell at i+1 or i+2, otherwise, if one buy i+1, one can only sell at i+2. start from i = 0 so we can find out the best profit.

    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            
            if len(prices) < 2:
                return 0
        
    
            buy = prices[0]
            sell = prices[1]
            profit = [max(sell-buy,0)]
            
            for i in range(1,len(prices)-1):
                if prices[i] < buy:
                    buy = prices[i]
                    sell = prices[i+1]
                else:
                    sell = max(sell, prices[i+1])
    
                if sell-buy > 0:
                    profit.append(sell-buy)
            
            return max(profit)
        
    

Log in to reply
 

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