121. Best Time to Buy and Sell Stock

代码如下：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        if len(prices) == 1:
            return 0
        minp= prices[0];
        profit = 0;
        for i in range(len(prices)):
            if prices[i] < minp:
                minp = prices[i]
            else:
                profit = max(profit, prices[i] - minp)
        return profit
        

动态规划的思想，每一步都是当前的最优值。代码如下：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0 or len(prices) == 1:
            return 0
        best_price = prices[0]
        max_profit = 0
        for p in prices:
            best_price = min(best_price, p)
            max_profit = max(max_profit, p - best_price)
        return max_profit