随笔(2)–Leetcode 121

老规矩，废话不说，先看题目吧

简单来讲，给你一个股票序列，交易规则是只能购买一次(先买后卖)，求你能获得的最大利润。明眼人看得出来就是找到这个序列的一个波峰和一个波谷，然后再相减。其实这个模型在实际中有很多应用，比如说求解maxmium drawdown.所以是很有可能被问到的。

先说一个最直观的解法，复杂度，就是任意选一个序列的两个点，遍历所有的可能，然后选择出最大值。但是我们希望一遍扫描后就能获得结果，那么这就需要思考一下。

一个直觉的想法是，一个序列有很多波峰(局部最大值)和波谷(局部最小值)，一个成功的交易策略一定是在一个局部最小值开仓，在一个局部最大值平仓。但是由于我们只能先买后卖，所以波谷要出现在波峰前面。那么我们可以定一个min_price，它会动态的记录所有的局部最小值。然后我们定义一个max_profit,它会反复更新每一个在最小值处开仓的当前最大利润，遍历完后即为全局最大利润。代码如下

class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit=0

    min_price=10000000
    for i in range(len(prices)):
        if prices[i]<min_price:
            min_price=prices[i]

        if (prices[i]-min_price)>max_profit:
            max_profit=prices[i]-min_price


    return max_profit