My Python solution, O(n) time, O(1) memory, quite fast

  • 1
    class Solution:
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
                maxSofar, openSolution = 0, [prices[0],prices[0]]
                return 0
            for p in prices[1:]:
                if p > openSolution[1]:
                    openSolution[1] = p
                elif p < openSolution[0]:
                    maxSofar = max(maxSofar, openSolution[1] - openSolution[0])
                    openSolution = [p, p]
            return max(maxSofar, openSolution[1] - openSolution[0])

    The idea is keeping a max profile so far and an area larger solution (Open solution). The open solution might be closed when we find a even lower buying price. When closing the current open solution, a new one should be opened.

Log in to reply

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