【python实现】 121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

思路：
在价格最低的时候买入，差价最大的时候卖出。
解答：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        profit = 0
        minimum = prices[0]
        for i in prices:
            minimum = min(i, minimum)
            profit = max(i - minimum, profit)
        return profit

使用两层循环的代码如下（结果显示超时）：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = 0
        s = []
        for i in range(0, len(prices)):
            for j in range(i, len(prices)):
                d = prices[j]-prices[i]
                if d>0:
                    s.append(d)
        if len(s) == 0:
            return 0
        else:
            return max(s)