Simple O(n) Python answer

  • 0

    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]
                    sell = max(sell, prices[i+1])
                if sell-buy > 0:
            return max(profit)

Log in to reply

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