Leetcode_121 Best Time to Buy an

假设你有一个数组，其中第 i 个元素是一支给定股票第 i 天的价格。

如果您只能完成最多一笔交易（即买入和卖出一股股票），则设计一个算法来找到最大的利润。

示例 1:

输入: [7, 1, 5, 3, 6, 4]
输出: 5

最大利润 = 6-1 = 5（不是 7-1 = 6, 因为卖出价格需要大于买入价格）

示例 2:

输入: [7, 6, 4, 3, 1]
输出: 0

在这种情况下, 没有交易完成, 即最大利润为 0。

"""
考察动态规划
记录两个值：
r：到目前位置最大的利润，默认0
lower：到目前位置最小的股票价格，默认第一个
遍历数据，当前价格-lower和r比较取最大利润，lower和当前价格比较取最小价格
"""

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        r = 0
        lower = prices[0]
        for i in range(1, len(prices)):
            r = max(prices[i] - lower, r)
            lower = min(prices[i], lower)
        return r