My own algorithm that does not use DP but runs as fast.

  • 0

    The idea is that the potential max profit is achieved when you buy at the lowest price prior to the current price and sell it. The real max profit is achieved when you are able to find the maximum profit among the potential max profit we calculated for every price point other than the price for the first day.

    def maxProfit(self, prices):
        if not prices:
            return 0
        min_, max_p = prices[0], 0
        for i in xrange(1, len(prices)):
            if prices[i - 1] < min_:
                min_ = prices[i - 1]
            if prices[i] - min_ > max_p:
                max_p = prices[i] - min_
        return max_p

Log in to reply

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