买卖股票的最佳时机

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

注意：你不能在买入股票前卖出股票。

示例  1:
        输入:  [7,1,5,3,6,4]
        输出:  5
        解释:  在第  2  天（股票价格  =  1）的时候买入，在第  5  天（股票价格  =  6）的时候卖出，最大利润  =  6-1  =  5  。
                  注意利润不能是  7-1  =  6,  因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例  2:
        输入:  [7,6,4,3,1]
        输出:  0
        解释:  在这种情况下,  没有交易完成,  所以最大利润为  0。

自我解答

        很显然，这是需要可以使用动态规划的最优解问题。
        思路与  "最大子序列和"类似，因为原问题的最大利润买入卖出组合有很多，每个组合都去统计太费时了，
        可以确定的是，卖出价格是其中的一个，因此可以把问题简单转化成：
                求出所有以每一天价格作为卖出价格的最大利润，记作  f(i)，
                在得到的数组中，利润最大则是原问题的解

自顶向下

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length < 2:
            return 0
        self.prices = prices
        self.max_profit = 0
        self.get_min_price_before(length - 1)
        return self.max_profit

    def get_min_price_before(self, j):
        if j == 0:
            return self.prices[j]
        min_price = self.get_min_price_before(j-1)
        profit = self.prices[j] - min_price
        if profit > self.max_profit:
            self.max_profit = profit
        return min_price if min_price < self.prices[j] else self.prices[j]

自底向上

class Solution2:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        min_price = prices[0]
        max_profit = 0
        for price in prices[1:]:
            profit = price - min_price
            if profit > max_profit:
                max_profit = profit
            if price < min_price:
                min_price = price
        return max_profit

原题链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock