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


  • 1
    B
    class Solution:
        # @param prices, a list of integer
        # @return an integer
        def maxProfit(self, prices):
            try:
                maxSofar, openSolution = 0, [prices[0],prices[0]]
            except:
                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.