Best time to buy and sell stock

Question

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Thoughts

I很简单，因为有时间关系，buy只能在sell之前

记录当前发现的最小值 如果 当前price-当前最小值 > 目前的最大利润，就记录

buy and sell stock系列

Solution

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        minPrice = sys.maxint
        maxProfit = 0
        for price in prices:
            if price < minPrice:
                minPrice = price
            if price - minPrice > maxProfit:
                maxProfit = price - minPrice
        return maxProfit