Best Time to Buy and Sell Stock

Problem: Best Time to Buy and Sell Stock

The profit we can make by selling the stock at a certain time is decided by price at this time and minimum price before. Thus, we iterate through the price list and keep maintaining minimum price to decide the profit. We can also keep the maximum profit and do updating while iterating through the list.

Note that if a price contribute the minimum buy, then it cannot contribute to maximum profit selling. Vice versa. The fact is quite easy to be proved.

Code in Python:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        max_profit, min_buy = 0, prices[0]
        for i in xrange(1, len(prices)):
            if prices[i] <= min_buy:
                min_buy = prices[i]
            else:
                if prices[i] - min_buy > max_profit:
                    max_profit = prices[i] - min_buy
        return max_profit