Leetcode121. 买卖股票的最佳时机

编程打卡第三天：

1.enumerate暴力搜索：

    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i, nums1 in enumerate(prices):
            for j, nums2 in enumerate(prices[i+1:]):
                result = max(result, prices[i+j+1]-prices[i])
        return result if result>=0 else 0

两个for循环超出时间限制

2. 动态规划

前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

求收益最大值不需要第i天和前i-1天每天都减，只需要和最小值相减，就能得到最大收益。因此减少了一个for循环。

注意： 求最值通常是用动态规划的方法求解

    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(1,len(prices)):
            history_min = min(prices[:i])
            result = max(prices[i]-history_min, result)
        return result if result >=0 else 0

依旧超时，超时就找循环结构里的i，原因在于min(prices[:i]),因为每次循环都要求一个全局最小值。而全局最小值只需比较第i天的数值和之前的最小值即可。

解法3：改进后的动态规划：

        result = 0
        history_min = prices[0]
        for i in range(1,len(prices)):
            history_min = min(prices[i],history_min)
            result = max(prices[i]-history_min, result)
        return result if result >=0 else 0