Very simple Python solution O(1) space, O(n) time


  • 1
    A

    This is simpler than I originally though. I iterate over each element in the prices list. Suppose, in the nth turn I sell the current element that I bought sometime before. If I want a good sell a need to select the minimum price before the nth day. But I can keep track of that minimum in a single variable (lowest). So I calculate the difference between the price of the current element and the lowest price before. The final result will be the maximum of these differences.

    def maxProfit(self, prices):
        result = 0
        if not prices: return result
        lowest = prices[0]
        for each in prices[1:]:
            result = max(result, each - lowest)
            lowest = min(each, lowest)
        return result

Log in to reply
 

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